[백준 22858] 원상 복구 (small) (C++)

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

문제

 P₁, P₂, ⋯, P_N의 수가 적혀 있는 N개의 카드가 있다.

1부터 N까지 수가 하나씩 존재하는 수열 D₁, D₂, ⋯,D_i, ⋯, D_N이 있다. 이때 각 i에 대해 D_i번째 카드를 i번째로 가져오는 작업을 셔플이라고 부른다.

예를 들어, P₁, P₂, ⋯, P_N이 1, 4, 5, 3, 2이고, D₁, D₂, ⋯, D_N가 4, 3, 1, 2, 5라고 가정해보자. 이 카드를 한번 섞으면 3, 5, 1, 4, 2가 된다. 아래 그림에서 S는 카드를 한 번 섞은 후를 의미한다.

 

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

입력

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

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

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

출력

원래 카드의 배치인 P₁부터 P_N까지의 값들을 공백으로 구분해서 출력한다.

제한

•  1 ≤ N ≤ 10⁴
•  1 ≤ K ≤ 10³
•  1 ≤ D_i ≤ N
•  1 ≤ P_i, S_i ≤ 10⁶
•  P_i는 정수

문제 풀이

---

구현 문제.

 

P의 D[i]번째 카드가 S의 i번째 카드가 된다. 따라서 D[i]로부터 S[i]의 원래 인덱스를 얻을 수 있고, 원소 자체의 값은 S[i]이다. 임시 배열 temp를 만들어 이전 과정이었을 배열을 저장하며, 셔플 이전의 상태를 여러 번 거쳐 원래의 P가 되도록 이를 K번 반복해주면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	int* P = new int[N];
	int* D = new int[N];
	int* temp = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> P[i];
	}
	for (int i = 0; i < N; i++)
	{
		cin >> D[i];
		temp[i] = 0;
	}
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int index = D[j] - 1;
			temp[index] = P[j];
		}
		for (int j = 0; j < N; j++)
		{
			P[j] = temp[j];
		}
	}
	for (int i = 0; i < N; i++)
	{
		cout << temp[i] << " ";
	}
	return 0;
}