728x90
https://www.acmicpc.net/problem/10973
10973번: 이전 순열
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
https://nyeoungkm.tistory.com/entry/백준c-10972번-다음-순열
[백준/c++] 10972번: 다음 순열
https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net..
nyeoungkm.tistory.com
다음 순열을 구하는 방법을 반대로 해주면 된다.
#include <iostream>
#include <algorithm>
#include <string>
#define MAX 10000
using namespace std;
int arr[MAX], n;
bool prev_permutation(){
int i = n-1;
while(i>0 && arr[i-1] < arr[i]) --i;
if(i<=0) return false; //완전 오름차순인 경우: 첫번째 순열
int j = n-1;
while(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(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i=0; i<n; i++) cin >> arr[i];
if(prev_permutation()){
for(int i=0; i<n; i++) cout << arr[i] << ' ';
cout << '\n';
}else{
cout << "-1\n";
}
return 0;
}
이것 역시 STL의 prev_permutation() 함수를 사용하면 간단하게 할 수 있다..
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define MAX 10000
using namespace std;
int arr[MAX], n;
vector<int> v;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i=0; i<n; i++) {
int x;
cin >> x;
v.push_back(x);
}
if(prev_permutation(v.begin(), v.end())){
for(int i=0; i<n; i++) cout << v[i] << ' ';
cout << '\n';
}else{
cout << "-1\n";
}
return 0;
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[백준/c++] 11723번: 집합 (0) | 2022.08.04 |
---|---|
[백준/c++] 10971번: 외판원 순회 2 (0) | 2022.08.04 |
[백준/c++] 10972번: 다음 순열 (0) | 2022.08.04 |
[백준/c++] 18290번: NM과 K(1) (0) | 2022.08.04 |
[백준/c++] 17425번: 약수의 합 (0) | 2022.08.04 |