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

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

22858번: 원상 복구 (small)

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

입력

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

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

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

출력

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

 

1. 풀이

간단한다. 카드 섞는 과정을 거꾸로 해서 코드로 구현하면 된다.

1.1. 로직

1. n과 k를 입력받는다.

2. n+1 크기만큼 s 배열과 d 배열을 선언하고 크기를 할당한다. 이후 사용할 tmp 배열도 선언하고 n+1 크기만큼 할당한다.

3. s[1] 부터 s[n] 까지 입력받는다.

4. d[1] 부터 d[n] 까지 입력받는다.

5. k번 아래 과정을 반복한다.

• 카드 섞기 전 원래 카드 배치를 tmp 배열에 저장: 1번부터 n번까지 tmp[d[j]] = s[j];
• tmp 배열을 s 배열에 복사 : s = Arrays.copyOf(tmp, n+1);

6. s[1] ~ s[n] 까지 출력

1.2.  

1.3. 코드

      

      

      

    
    

      <java />
    
import java.io.*;
import java.util.*;

public class Main {
	

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[] s = new int[n+1];
        int[] d = new int[n+1];
        
        int[] tmp = new int[n+1];
        
        // s 배열 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
        	s[i] = Integer.parseInt(st.nextToken());
        }
        
        // d 배열 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
        	d[i] = Integer.parseInt(st.nextToken());
        }
        
        // 카드 섞는 과정을 k번 거꾸로 함
        for (int i = 0; i < k; i++) {
        	
        	// 카드 섞기 전 원래 카드 배치를 tmp 배열에 저장
        	for (int j = 1; j <= n; j++) {
        		tmp[d[j]] = s[j];
        	}
        	
        	// tmp 배열을 s 배열에 복사
        	s = Arrays.copyOf(tmp, n+1);
        }
        
        for (int j = 1; j <= n; j++)
        	bw.write(s[j] + " ");
        
        
        bw.flush();
        bw.close();
        br.close();

    }
}