[BOJ] 10972, 10973 다음 순열 / 이전 순열

*이전 순열의 경우에는 맨 뒤의 인덱스부터 이전 인덱스와 비교하면서 뒤쪽에 나보다 작은 수가 존재하는 경우가 자리를 바꾸는 경우이다. 

-> 4 자리의 순열일 경우 

1 2 3 4 라면 0번 인덱스의 값인 [1]이 가장 작은 값이므로 뒤에 이보다 작은 값이 없다.

즉, 가장 처음 순열이라는 것이다. 

 

*이런 특성을 이용해서 idx를 찾는다.

*이 idx와 자리를 바꿀 인덱스를 찾아야 한다. 

바로 이전이라고 했기 때문에 idx보다 뒤에 있으면서 큰 수를 찾아야 한다. n부터 idx까지 비교하면서 idx의 값보다 작으면서 가장 뒤에있는 수를 찾는다. 

4 2 1 3 일 때 idx는 2가 된다. (바로 뒤에 1이라는 작은 수가 있기 때문에)

idx2는 2보다 뒤에 있으면서 2보다 작은 수인 1이 된다. 

 

*여기까지 idx와 idx2가 구해졌다. 

이 둘을 바꾼다. (swap)

=:> 4 1 2 3 

하지만 이게 정답은 아니다. 바로 이전이라고 했기 때문에 이전의 순열 중 가장 큰 값이 되어야 하기 때문이다. 

 

*idx+1에서 n까지 내림차순으로 정렬한다. 

 

*다음 순열은 이전 순열과 부등호만 반대로 하면 된다. 

이전 순열

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int fact[10001]; int seq[10001], sorted[10001]; bool visited[10001]; bool compare(const int& a, const int& b) { return a > b; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &seq[i]); //sorted[i] = seq[i]; } int idx = 0, idx2 = 0; for (int i = n - 2; i >= 0; i--) { //자기자신보다 작은 숫자가 뒤에 잇는 경우 뒤에 있는 숫자 중 가장 뒤쪽에 있는 작은 수와 자리를 바꾼다. if (seq[i] > seq[i + 1]) { idx = i; break; } } if (idx == 0 && seq[0] == 1) { printf("%d", -1); return 0; } for (int i = n-1; i > idx; i--) { if (seq[i] < seq[idx]) { idx2 = i; break; } } /*sort(sorted, sorted + n); do { for (int i = 0; i < n; i++) printf("%d ", sorted[i]); printf("\n"); } while (next_permutation(sorted, sorted + n));*/ swap(seq[idx], seq[idx2]); sort(seq + idx + 1, seq + n, compare); for (int i = 0; i < n; ++i) { printf("%d ", seq[i]); } return 0; }

다음 순열

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int main() { int n; scanf("%d", &n); int seq[10001] = { 0 }, sorted[10001] = { 0 }; for (int i = 0; i < n; i++) { scanf("%d", &seq[i]); //sorted[i] = seq[i]; } /*sort(sorted, sorted + n); do { for (int i = 0; i < n; i++) printf("%d ", sorted[i]); printf("\n"); } while (next_permutation(sorted, sorted + n));*/ int idx = 0, idx2 = 0; for (int i = n - 2; i >= 0; i--) { if (seq[i] < seq[i + 1]) { idx = i; break; } } if (idx == 0 && seq[0] == n) { printf("%d", -1); return 0; } for (int i = n - 1; i > idx; i--) { if (seq[i] > seq[idx]) { idx2 = i; break; } } swap(seq[idx], seq[idx2]); sort(seq + idx + 1, seq + n); for (int i = 0; i < n; ++i) printf("%d ", seq[i]); return 0; }