[알고리즘 풀이 분석] BOJ 22858 원상복구

nnnyeong·2021년 12월 11일
0

알고리즘 풀이분석

목록 보기
89/101

오랜만에 다시 푸는 알고리즘! 간단한 구현 문제 BOJ 22858 원상복구를 풀어보았다!




BOJ 22858 원상복구

수가 적혀있는 P1,P2,...,PNP_1, P_2, ..., P_N NN개의 카드가 있다.

1부터 N까지 수가 하나씩 존재하는 D1,D2,...,Di,...DND_1, D_2, ... , D_i , ... D_N 가 있다. 이때 DiD_iPDiP_{D_i} 값을 ii 번째로 가지고 오는 것을 의미한다. 이러한 작업을 카드 섞기라고 부른다. 카드를 섞는 작업은 동시에 진행된다.

예를 들어, P1,P2,...,PNP_1, P_2, ..., P_N이 1, 4, 5, 3, 2이고, D1,D2,...,DND_1, D_2, ..., D_N가 4, 3, 1, 2, 5라고 가정해보자. 이 카드를 한번 섞으면 3, 5, 1, 4, 2가 된다. 아래 그림에서 SS는 카드를 한 번 섞은 후를 의미한다.

위 방식을 그대로 KK번 섞은 카드의 정보와 DD의 정보를 알고 있다고 할 때, 원래 카드는 어떤 배치를 이루고 있었는지 구해보자.




입출력

[입력]
첫번째 줄에는 카드의 개수 NN과 카드를 섞은 횟수인 KK가 공백으로 구분되어 주어진다.
두번째 줄에는 KK번 카드를 섞은 후 카드의 배치를 의미하는 SiS_i가 공백으로 구분되어 총 NN개 주어진다.
세번째 줄에는 총 N개의 DiD_i이 공백으로 구분되어 주어진다.

[출력]
원래 카드의 배치를 P1P_1부터 PNP_N의 값들을 공백으로 구분해서 출력한다.

[제한]
1N1041 \le N \le 10^4
1K1031 \le K \le 10^3
1DiN1 \le D_i \le N
1Pi,Si1061 \le P_i, S_i \le 10^6




나의 풀이

알고리즘 자체는 간단했다. 실버 3단계 문제였기 때문에 특별히 어려울 것은 없었다. 주어진 방식을 거꾸로 실행해보면 S[i] 값은 원래 D[i] 위치에 존재해야 한다는 것을 쉽게 알 수 있다!

입력으로 주어지는 S 배열을 k 번 거꾸로 돌려서 마지막 결과를 출력해주면 된다.

입력 값이 크다면 추가적인 배열을 쓰는 것을 고민했겠지만 그리 크지 않았기 때문에 매번 새로운 배열에 담은뒤 대체하는 형식으로 진행해주었다.




코드

#include <iostream>
#include <vector>

// boj 22858 원상 복구, 실버 3, 구현
using namespace std;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin>>N>>K;

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

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

    vector<int> rewind(N+1, 0);
    while (K>0){
        K--;
        for (int i = 1; i <= N; ++i) {
            int origin_index = D[i];
            int num = S[i];
            rewind[origin_index] = num;
        }

        S = rewind;
    }

    rewind.clear();

    for (int i = 1; i <= N; ++i) {
        cout<<S[i]<<' ';
    }
    cout<<'\n';

   return 0;
}
profile
주니어 개발자까지 ☄️☄️

0개의 댓글