문제링크
길이가 인 수열()이 주어진다.
각 수열의 값은 으로 이루어져 있다.
수열의 배치를 바꾸어서 새로운 수열()을 만들되 , , , 이어야 한다.
새로운 수열 중 사전 순으로 가장 빠른 수열을 구하여라.
알고리즘은 간단하다.
(길이가 1이면 다른 경우가 없으므로 따로 예외처리 해주었다.)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int tc;
int n;
int permutation[1001];
int ansPermutation[1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> tc;
for (int tcCnt = 1; tcCnt <= tc; ++tcCnt) {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> permutation[i];
ansPermutation[i] = i;
}
if (n == 1) { // 예외 처리
cout << -1 << '\n';
continue;
}
while (true) {
bool flag = true;
for (int i = 1; i <= n; ++i) {
if (ansPermutation[i] == permutation[i]) {
if (i == n) swap(ansPermutation[i - 1], ansPermutation[i]);
else swap(ansPermutation[i], ansPermutation[i + 1]);
flag = false;
}
}
if (flag) break;
}
for (int i = 1; i <= n; ++i)
cout << ansPermutation[i] << ' ';
cout << '\n';
}
}
사실 보기보다 푸는데 오래 걸렸다.
처음엔 next_permutation 함수를 이용해서 쉽게 가려다 TLE되었고 그 다음 그리디하게 풀려고 시도도 했었다.
쉽게 가려고 생각안했으면 오히려 빨리 풀었을 거 같은 문제