[Java] 백준 22858번 - 원상 복구 (small)

#22858 - 원상 복구 (small)

---

난이도 : 실버 3

문제 유형 : 구현

 

https://www.acmicpc.net/problem/22858

 

문제 분석

---

문제가 난잡하게 설명돼있는데 

 

D = [4, 3, 1, 2, 5]

P = [1, 4, 5, 3, 2]

일 때

S[] 가 결정되는 방식은

 

 1~N까지의 수가 하나씩 존재하는 수열 D1,D2 ... Dn 이 있을때 , 각 i에 대해 Di 번째 카드를 i번째로 가져오는 작업을 셔플이라고 한다.

 

i = 1일때 D1은 4이고, Di 번째 카드를 i번째로 가져온다했으니 P에서 4(D1)번째카드를 S의 1(i)번째로 옮기는 것이다.

그래서 i= 1 일때 S는 S = [3,0,0,0,0] 가 된다.

 

i = 2 일때는 D2는 3이고, P에서 3(D2)번째카드를 S의 2(i)번째로 옮기는 것, 그래서 S = [3,5,0,0,0] 이 된다. 

 

이 과정에서 S[i] = P[D[i] - 1] 이 나오는 것을 확인할 수 있다. 

 

우리가 구해야할 건 "D와S가 주어지고 셔플 횟수가 주어졌을때 P를 구하는 것"이다.  

 

위에서 나왔던 S[i] = P[D[i] - 1]  식을 역으로 생각해주면

P[D[i] - 1] = S[i] 

가 나오게 된다.

 

이를 셔플 횟수만큼 반복해주면 P를 구할 수 있게된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int n,k;
    static int shuffled[];
    static int origin[];
    static int tmp[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] st = br.readLine().split(" ");
        n = Integer.parseInt(st[0]);
        k = Integer.parseInt(st[1]);
        shuffled = new int[n]; // S 배열
        origin = new int[n]; // D 배열
        tmp = new int[n]; // P 배열

        st = br.readLine().split(" ");
        for(int i =0; i<n; i++){
            shuffled[i] = Integer.parseInt(st[i]);
        }
        st = br.readLine().split(" ");
        for(int i =0 ;i<n;i++){
            origin[i] = Integer.parseInt(st[i]);
        }
        
        for(int j = 0 ;j<k;j++){ // 셔플 횟수 K번만큼 반복
            for(int i= 0;i<n;i++){
                tmp[origin[i]-1] = shuffled[i]; // P[D[i]-1] = S[i] 적용
            }
            shuffled = Arrays.copyOf(tmp, tmp.length); // S[i]는 셔플할때마다 바뀌게됨
        }
        for(int i =0 ;i<n;i++){
            System.out.print(tmp[i] + " ");
        }
    }

}