백준 10972, 10973 다음순열/이전순열 java

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

 

https://www.acmicpc.net/problem/10973

10973번: 이전 순열

 

 

두 문제는 결과코드가 부등호 방향만 다른 문제이다.

 

예를들어서 , 7 2 3 6 5 4 1 의 다음 순열을 찾는다고 가정해보자.

 

맨 마지막 자릿수부터 살펴보면 1 , 4 , 5 ,6 까지 오름차순으로 이어지다가  3이 나오는 순간 오름차순이 아니게 된다.

이는 7 2 3 으로 시작하는 수열의 마지막이  7 2 3 6 5 4 1 이라는 뜻이다.

이 점을 이용해서 문제를 해결하면 된다.

 

*10972번 기준 간단 설명*

1. 위 설명처럼 1의자리부터 올라가면서 수열의 오름차순이 끝나는 지점을 찾아 변수에 저장한다.

2. 또 다른 변수를 선언하여 1의자리 숫자를 저장한다.

3. 수열의 오름차순이 끝나는 지점을 저장한 변수와, 2번 변수를 이용하여 다음 수열로 가기 위한 작업을 한다.

4. 다음 순열로 가기 위한 작업은, 마지막 오름차순 자리에서 1을 뺀 값, 즉 바로 이전자리와 오름차순을 이어오던 수열들 중에서 가장 작은 수와 swap 한다.

5. swap을 완료 한 후 ,  두 변수가 엇갈릴 때 까지 swap을 다시 진행한다.

 

 

import java.util.Scanner;

public class Exam10972 {

	static boolean next_number(int[] a) {
		int i = a.length - 1;
		while (i > 0 && a[i - 1] >= a[i]) {
			i-=1;
		}

		if (i < 0) {
			return false;
		}

		int j = a.length - 1;

		while (a[j] <= a[i - 1]) {
			j-=1;
		}

		int temp = a[i - 1];
		a[i - 1] = a[j];
		a[j] = temp;

		j = a.length - 1;

		while (i < j) {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j--;
		}

		return true;

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 수열의 갯수 입력
		int[] a = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}

		if (next_number(a)) {
			for (int i = 0; i < n; i++) {
				System.out.print(a[i] + " ");
			}
		} else {
			System.out.println(-1);
		}
	}
}

import java.util.Scanner;

public class Exam10973 {
	static boolean before_number(int[] a) {

		int i = a.length - 1;
		while (i > 0 && a[i] >= a[i - 1]) {
			i--;
		}

		if (i <= 0) {
			return false;
		}

		int j = a.length - 1;
		while (a[i - 1] <= a[j]) {
			j--;
		}
		int temp = a[i - 1];
		a[i - 1] = a[j];
		a[j] = temp;

		j = a.length - 1;
		while (i < j) {

			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j--;

		}
		return true;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 수열의 갯수 입력
		int[] a = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}

		if (before_number(a)) {
			for (int i = 0; i < n; i++) {
				System.out.print(a[i] + " ");
			}
		} else {
			System.out.println(-1);
		}
	}
}