[BOJ] 22858: 원상 복구 (small) (JAVA)

문제

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

 

여담

문제 이해만 하면 쉽게 풀 수 있는 문제였는데 문제 자체를 이해하지 못해서 시간을 좀 날렸다..ㅎㅎ 독해력 대체 무슨일이야

풀이

문제에 따르면 "Di번째 카드를 i번째로 가져오는 것이 셔플"이라고 한다. 개인적으로 이 문장을 이해하는게 조금 어려웠기 때문에 예제로 주어진 입력에 설명을 덧붙여보겠다. 

• i가 1인 경우
  • D1번째 카드를 1번째로 가져와야 함 (D[1] = 4)
  • 즉, 4번째 카드를 1번째로 가져와야 함
  • S[1] = P[D[1]] = P[4] = 3

• i가 2인 경우
  • D2번째 카드를 2번째로 가져와야 함 (D[2] = 3)
  • 즉, 3번째 카드를 2번째로 가져와야 함
  • S[2] = P[D[2]] = P[3] = 5
• ...
• i가 5인 경우
  • D5번째 카드를 5번째로 가져와야 함 (D[5] = 5)
  • 즉, 5번째 카드를 5번째로 가져와야 함
  • S[5] = P[D[5]] = P[5] = 2

 

우리는 셔플된 카드를 원래 상태로 복구시키는 것이므로 해당 문장을 뒤집어서 풀이하면 된다. 즉, "i번째 카드는 Di번째에 있었다"라는 뜻을 가지게 된다. 

 

따라서 아래의 식을 통해 1번부터 N번 카드의 원래 위치를 구하면 된다. (K번 반복하면 된다)

• P[D[i]] = S[i] (1 ≤ i ≤ N)

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, K;
    static int[] D, S, P;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        D = new int[N + 1];
        S = new int[N + 1];
        P = new int[N + 1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            S[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            D[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < K; i++) {
            for (int j = 1; j <= N; j++) {
                P[D[j]] = S[j];
            }
            S = P.clone();
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(P[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
}

---