[Codeforces #798] B. Mystic Permutation

tolelom·2022년 6월 26일
0

코드포스

목록 보기
1/4

문제 설명

문제링크
길이가 nn인 수열(pp)이 주어진다.
각 수열의 값은 1n1 \sim n으로 이루어져 있다.

수열의 배치를 바꾸어서 새로운 수열(qq)을 만들되 p1q1p_1 \neq q_1, p2q2p_2 \neq q_2, \ldots, pnqnp_n \neq q_n 이어야 한다.
새로운 수열 중 사전 순으로 가장 빠른 수열을 구하여라.

알고리즘

알고리즘은 간단하다.

  1. 수열 qqq1=1q_1=1, q2=2q_2 = 2, \ldots, qn=nq_n = n으로 만든다. (사전 순으로 가장 빠른 상태)
  2. pi=qip_i = q_i인 쌍이 존재하는 동안 앞에서 뒤로 순회하며 pi=qip_i = q_i인 쌍을 찾으면 swap(qi,qi+1swap(q_i, q_{i+1}) 한다. (단 i=ni = n일 경우 swap(qi,qi1)swap(q_i, q_{i-1}))

(길이가 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되었고 그 다음 그리디하게 풀려고 시도도 했었다.
쉽게 가려고 생각안했으면 오히려 빨리 풀었을 거 같은 문제

profile
이것 저것 작성하는 기술 블로그

0개의 댓글