1 <= N <= 10,000 범위의 N과 순열이 주어집니다. 주어진 순얼의 이전에 오는 순열을 출력하는 문제입니다.
만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력합니다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같습니다.
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
입력:
5
5 4 3 2 1
출력:
5 4 3 1 2
🔔 Kick Point :
이전 순열은 어떻게 구할 수 있는지 수가 증가하는 조건을 잘 생각해 보면 됩니다.
N = 3 인 경우에,
1 2 3 에서 3 2 1 인 수로 가기에 가장 적은 숫자에서 가장 큰 수로 가게 됩니다.
따라서 이전의 수를 구하기 위해서는 가장 직전의 적은 숫자를 구하면 되는 것입니다.
가장 직전의 적은 숫자를 구하려면 수가 줄어드는 조건을 찾으면 되는데요.
저 같은 경우는 직접 나열하여 조건을 찾았습니다.
N = 3 인 경우에
1 3 2 -> 1 2 3 이 되는 경우를 살펴봅시다
여기서 앞의 범위 A 뒤의 범위 B로 나누겠습니다. 뒤의 범위는 오름차순(뒤에서부터는 내림차순)이 되는 숫자 까지입니다.
예를 들어
1 2 3 4 5 인 경우 B의 범위가 {1, 2, 3, 4, 5}입니다
1 2 4 3 5 이면 B의 범위는 { 3 5 } 입니다.
5 1 2 3 4 이면 B의 범위는 {1, 2, 3, 4} 입니다.
A의 범위는 B의 나머지 범위라 생각하면 됩니다.
다시 문제로 돌아가
132에서
1) 세번째 자리 수인 2가 두번째 자리 수 3인보다 작은 상황입니다. 3 > 2 즉 내림차순이기에
앞의 범위는 A: {1, 3} 뒤의 범위는 B: {2} 로 두었습니다.
2) A범위에서 마지막번째 수를 x라 하고 B의 범위에서 x보다 적으면서, 가장 차이값이 적는 값을 y라 하겠습니다.
여기서 x는 3이고, y는 2입니다.
3) x와 y를 교환해줍니다 A {1, 2} B {3} 이렇게 되죠
4) B를 오름차순으로 정리해줍니다.
그러면 이전의 수를 구할 수 있습니다.
순서 2번에서 헷갈리실까봐
5 1 2 3 4 를 예로 들자면
A: {5} B: {1 2 3 4} 이고
x = 5 , y = 4가 되는 것이죠
🔔 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 pre_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;
while (j >= i && Arr[i - 1] < Arr[j]) {
--j;
}
swap(Arr[i - 1], Arr[j]);
for (int k = i, h = N - 1; k < h; ++k, --h) {
swap(Arr[k], Arr[h]);
}
return true;
}
int main() {
int N;
int Arr[MAX];
cin >> N;
Input(Arr, N);
if (pre_permutaion(Arr, N)) {
for (int i = 0; i < N; i++) {
cout << Arr[i] << ' ';
}
}
else {
cout << -1;
}
}
