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

Explain

1부터 N까지의 수로 이루어진 순열이 있다. 이 떄, 사전순으로 다음에 오는 순열을 구해보자!
사전순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

여기서 사전순이란 N=3인 경우에 사전순으로 나열하면 아래와 같다.

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

C++에서는 STL의 next_permutation을 사용하면 되지만, Java에서는 직접 구현해서 사용하면 된다.
직접 next_permutation 함수를 구현해서 다음 순열을 구하면 된다.

Key Point

순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열을 찾는 방법과 똑같다.

  1. i는 가장 오른쪽[마지막]원소부터 시작하며 a[i-1]< a[i]를 만족하는 가장 큰 i를 찾는다.
    즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾아야 한다.
    7 2 3 6 5 4 1
    여기서는 i:6, i-1:3이 된다.
  2. j>=i이면서 a[j]>a[i-1]를 만족하는 즉, i-1의 오른쪽에서 i-1보다 크면서 거기서 가장 작은 수를 찾는다.
  3. a[i-1]과 a[j]를 swap한다.
  4. a[i]부터 순열을 뒤집는다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Exam10972 {

	public static boolean next_permutation(int[] a) {
		int i = a.length - 1;
		while(i>0 && a[i-1]>=a[i]) {
			i--;
		}
		if(i<=0) {
			return false;
		}
		
		int j = a.length-1;
		while(a[j]<=a[i-1]) {
			j--;
		}
		
		int tmp = a[i-1];
		a[i-1] = a[j];
		a[j] = tmp;
		
		j = a.length-1;
		while(i<j) {
			tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
			i++;
			j--;
		}
		return true;
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(bf.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		if(next_permutation(arr)) {
			for(int i=0;i<N;i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
		}else {
			System.out.println("-1");
		}
	}
}