다음 순열 (10972번)
https://www.acmicpc.net/problem/10972
풀이방법
- 주어진 입력 순열의 다음 순열을 구하는 문제이다.
- 모든 순열을 구하면서 입력받은 순열의 다음 순열을 구하게 되면 시간이 오래 걸리게 된다.
- 최악의 경우: 역순으로 입력받은 경우
- 위와 같은 방법으로는 시간이 오래 걸리기 때문에 다른 방법을 찾아봐야 한다.
[1, 2, 3, 4, 5]로 이루어진 순열을 생각해보면1XXXX,2XXXX,3XXXX,4XXXX,5XXXX순으로 순열이 이루어져야 한다.1XXXX는 다시12XXX,13XXX,14XXX,15XXX로 이루어지고2XXXX는 다시21XXX,23XXX,24XXX,15XXX로 이루어진다.- 위
X들은 오름차순이 되어야 한다.
- 위의 내용을 토대로
[3, 2, 5, 4, 1]이 주어졌을 때 이 순열의 다음 순열은[3, 4, 1, 2, 5]가 되어야 한다.- 그 이유는
32XXX를 생각했을 때XXX가 모두 내림차순이므로 위[3, 2, 5, 4, 1]은32XXX로 시작하는 모든 수열에서 마지막이기 때문이다. 32XXX의 다음 순열은34XXX가 되어야 하고,34XXX로 시작하는 순열 중 제일 첫번째인[3, 2, 5, 4, 1]의 다음 순열은[3, 4, 1, 2, 5]가 된다.
- 그 이유는
- 위 예시를 잘 보면 결국
[3, 2, 5, 4, 1]에서 처음으로32XXX보다 큰 값이 나올 수 있는 값은34XXX이므로2와4를 서로 교환하면[3, 4, 5, 2, 1]이 되고34XXX로 시작하면서 제일 작은 수는[3, 4, 5, 2, 1]에서5, 2, 1을 역순으로 한 것이므로 뒤집어주면 된다.
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N];
int index = 0;
while (st.hasMoreTokens()) {
arr[index++] = Integer.parseInt(st.nextToken());
}
StringBuilder sb = new StringBuilder();
if (next_permutation(arr)) {
for(int i : arr) {
sb.append(i).append(' ');
}
System.out.println(sb);
}
else {
System.out.println(-1);
return;
}
}
private static boolean next_permutation(int[] arr) {
int i = arr.length-1;
// 뒤에서부터 탐색했을 때 처음으로 오름차순이 아닌 부분 검색
// [3, 2, 5, 4, 1]에서 32XXX 부분이 됨
while (i>0 && arr[i-1] > arr[i]) {
i--;
}
// 순열의 마지막부터 첫번째까지 갔을 경우 모두 오름차순이므로 false 반환
// 첫번째부터 순열의 마지막까지는 내림차순이 되므로
if (i <= 0) {
return false;
}
// 처음으로 오름차순이 아닌 부분보다 큰 값이 있을 경우 서로 교환
// [3, 2, 5, 4, 1]에서 4가 2보다 크므로
int j = arr.length-1;
while (arr[j] < arr[i-1]) {
j--;
}
swap(arr, i-1, j);
// 오름차순이 아닌 부분 이후의 값들을 모두 역으로 교환
reverse(arr, i);
return true;
}
private static void swap(int[] arr, int idx1, int idx2) {
int a1 = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = a1;
}
private static void reverse(int[] arr, int startIndex) {
int endIndex = arr.length-1;
while (startIndex <= endIndex) {
swap(arr, startIndex++, endIndex--);
}
}
}
Comments powered by Disqus.