백준 22858[자바] java 원상 복구 (small)

문제 링크: https://www.acmicpc.net/problem/22858

22858번: 원상 복구 (small)

▶문제

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

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

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

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

▶입력

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

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

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

▶출력

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

▶해설

이전의 것을 주어진 횟수에 맞춰서 만들어가면 되는 문제입니다. 조건을 살펴보겠습니다.

 

1. P(Di)의 값을 i로 옮긴다.

2. 이 과정을 반대로 수행한다. 

 

문제를 접했을 때 문장이 이해가 가지 않았지만 직접 작성해보며 깨달았습니다. 예제를 보며 이해해보겠습니다. 

 

D = 4 3 1 2 5 

P = 1 4 5 3 2

 

위와 같이 있을 때 순서대로 i=1~5까지 진행합니다. 

 

i =1 일 때 D1 = 4이며 P4은 3입니다. 따라서 D1의 값이 P의 index로 들어가고, 해당 값의 위치는 i라고 정의됩니다. 

이를 토대로 m번 진행해서 2번째 줄 입력이 되었습니다. 저희는 이것의 역순으로 m번 해서 출력하면 됩니다.

 

따라서 새로운 배열을 정의하고 방법의 역순으로 돌린 후 원래의 배열에 넣어주면 됩니다. 

private static void simul(){
    temp = new int[n+1];

    for(int i=1; i<=n; i++){
        temp[changes[i]] = arr[i];
    }
    arr = temp;
}

 

전체 코드

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




public class Main {


    static int n,m;
    static int [] changes;
    static int [] arr;
    static int [] temp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");

        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        arr = new int[n+1];
        changes = new int[n+1];

        String[] s1 = br.readLine().split(" ");
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(s1[i-1]);
        }

        String[] s2 = br.readLine().split(" ");
        for(int i=1; i<=n; i++){
            changes[i] = Integer.parseInt(s2[i-1]);
        }

        for(int i=0; i<m; i++){
            simul();
        }

        for(int i=1; i<=n; i++){
            System.out.print(arr[i]+" ");
        }
    }


    private static void simul(){
        temp = new int[n+1];

        for(int i=1; i<=n; i++){
            temp[changes[i]] = arr[i];
        }
        arr = temp;
    }
}