반응형

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 이전 순열 (10973)
10973번: 이전 순열
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
[ 문제 ]
1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
- 1, 2, 3
- 1, 3, 2
- 2, 1, 3
- 2, 3, 1
- 3, 1, 2
- 3, 2, 1
[ 입력 ]
- 첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.
[ 출력 ]
- 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
[ 코드 1 ]
#include<iostream> #include<algorithm> #include<vector> using namespace std; bool last_permutation(vector <int>& a, int n) { int i = n - 1; while (i > 0 && a[i - 1] < a[i]) { i -= 1; } if (i == 0) { return false; } int j = n - 1; while (a[i - 1] <= a[j]) { j -= 1; } swap(a[i - 1], a[j]); j = n - 1; while (i<j) { swap(a[i], a[j]); i += 1; j -= 1; } return true; } int main() { int n; cin >> n; vector <int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } if (last_permutation(a, n)) { for (int i = 0; i < n ; i++) { cout << a[i] << ' '; } } else { cout << "-1"; } return 0; }
[ 코드 2 ]
#include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { int n; cin >> n; vector <int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } if (prev_permutation(a.begin(),a.end())) { for (int i = 0; i < n ; i++) { cout << a[i] << ' '; } } else { cout << "-1"; } return 0; }
반응형
'문과 코린이의, [C. C++] 기록 > C++ 백준 문제풀이' 카테고리의 다른 글
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 차이를 최대로 (10819) (0) | 2021.08.16 |
---|---|
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 모든 순열 (10974) (0) | 2021.08.16 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 다음 순열 (10972) (0) | 2021.08.16 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - N과 M(12) (15666) (0) | 2021.08.16 |
[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - N과 M(11) (15665) (0) | 2021.08.16 |