[BOJ] 원상 복구 (small) 22858번 C++

 

문제

 

 

입력

첫번째 줄에는 카드의 개수 N과 카드를 섞은 횟수인 K가 공백으로 구분되어 주어진다.

두번째 줄에는 K번 카드를 섞은 후 카드의 배치를 의미하는 Si가 공백으로 구분되어 총 N개 주어진다.

세번째 줄에는 총 N개의 Di이 공백으로 구분되어 주어진다.

 

출력

 

원래 카드의 배치인 P1$P_1$부터 PN$P_N$까지의 값들을 공백으로 구분해서 출력한다.

 

 

접근 방식

 

카드를 K번 원상 복구를 시키면 된다.

이때, 카드의 셔플 정보를 나타내는 D 배열을 이용해 반대를 구하면 되는데

만약 D가 4 3 1 2 5 이렇게 되어있다면,

역순 배열은 3 4 2 1 5 인 것이다.

 

이를 이용하면 간단하게 구할 수 있다..!

 

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N,K; cin>>N>>K;

    vector<int> S(N+1), D(N+1), rev(N+1), tmp(N+1);

    for(int i=1; i<=N; i++) cin>>S[i];
    for(int i=1; i<=N; i++) cin>>D[i];

    for(int i=1; i<=N; i++) {
        rev[D[i]] = i;
    }

    for(int i=1; i<=N; i++) {
        int idx = i;
        for(int t=0; t<K; t++) {
            idx = rev[idx];
        }
        tmp[i] = S[idx];
    }

    for(int i=1; i<=N; i++) cout<<tmp[i]<<" ";


}