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

Key Point

모든 순열을 구하는 문제를 반대로 생각해서 풀면된다.

Explain
모든 순열을 구할 때와 반대로 생각하면 된다.
1 2 3 4
이 경우 이전 순열은 없으므로 -1을 출력하면 된다.

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
52
53
public class Exam10973 {

	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");
		}

	}

}