이때 주어진 순열의 다음 순열을 출력하는 문제입니다. 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력합니다.
입력:
4
1 2 3 4
출력:
1 2 4 3
🔔 Kick Point :
DFS을 짜서 일일히 해보려다가 N이 너무 크기에 시간초과가 발생하여 실패했었습니다.
그래서 다른 분들의 도움을 받아보니, 수의 특징을 잘 살펴보면 쉽게 풀 수 있는 문제였습니다.
조건 찾는게 너무 어렵더라구요, 일일히 수를 나열해서 수가 증가하는 조건을 찾아보면 좋을 것 같습니다.
예를 들어 N이 4인 경우
1 < 2 < 3 < 4 가 첫번째 순서이고
4 > 3 > 2 > 1 이 마지막 순서입니다.
2 < 3 < 4 > 1 이란 중간 수를 예시로 다음수를 찾아보면
2 < 4 < 1 > 3 입니다.
이때 수의 범위를 뒤에서부터 내림차순 인 경우를 B, 그 외를 A로 나눠봅시다.
4 1 이란 수까지 내림차순 이기때문에 B는 {4, 1} A는 그 외의 범위인 {2, 3}이 됩니다.
A: { 2 3 } B: { 4 1 } 라고 생각하고,
A범위 제일 마지막 번째 수인 3보다 B범위 숫자들중 적은 차이로 큰 수를 찾으면 됩니다.
즉 여기선 4를 찾았습니다 (이때 B의 범위는 >로 이루어져 있기에 뒤에서부터 찾으면 됩니다)
여기서 3과 4를 바꿔주면
A {2 4} B { 3 1} 이 됩니다.
마지막으로 B의 수를 오름차순으로 정리해주면
A {2 4} B {1 3} 로 2 3 4 1 -> 2 4 1 3인 다음 수가 되는 것을 알 수 있습니다.
다른 수인 1 2 3 4 도 A {1, 2, 3} B {4} 로 생각하면 됩니다.
하지만 4 3 2 1 은 모두 내림차순이기 때문에 마지막 번째가 됩니다.
🔔 Code :
#include <iostream>
#define MAX 10000
using namespace std;
void Input(int Arr[], int N) {
for (int i = 0; i < N; i++) {
cin >> Arr[i];
}
}
bool next_Permutaion(int Arr[], int N) {
int i = N - 1;
// 뒤에서 부터 시작 하는 범위 찾기 // 내림차순
while (i > 0 && Arr[i - 1] > Arr[i]) {
i--;
}
if (i == 0) return false;
int j = N - 1;
// i번째 수 바로 앞의 수보다 큰 수 찾기
while (Arr[i -1] > Arr[j]) {
--j;
}
swap(Arr[i - 1], Arr[j]);
// i 번째 수부터 마지막까지 모두 뒤집기
for (int k = i, h = N - 1; k < h; k++, h--) {
swap(Arr[k], Arr[h]);
}
return true;
}
int main() {
int Arr[MAX];
int N;
cin >> N;
Input(Arr, N);
if (next_Permutaion(Arr, N)) {
for (int i = 0; i < N; i++) {
cout << Arr[i] << ' ';
}
}
else {
cout << -1;
}
}