[알고리즘/구현] 22858번 : 원상 복구(small) - python

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

22858번: 원상 복구 (small)

 

---

• 문제
• 소요시간: 30분 12초

---

• 설계하기(접근방법) 

1. 입력받기

1) 카드의 개수 n과, 섞은 횟수 k

2) k 번 섞은 후의 카드의 배를 의미하는 Si 가 N개 주어짐

3) N개의 Di가 공백으로 주어짐

 

2. 구현 및 해석

1) 예시 해석

1 번째 (i = 1) : D1 = 4, P4 = 3, S1 = 3

 

즉 보기 쉽게 나타낸다면

D는 카드를 섞을 위치를 정해주는 P에 대한 포인터이다.

그리고 D는 순서대로 배치되어 있기에

D = (1,4), (2,3), (3,1), (4,2) (5,5)로 앞에 순서를 추가해서 나타내준다면

1. P4의 값을 P1로 보내라

2. P3의 값을 P2로 보내라

3. P1의 값을 P3으로 보내라

4. P2의 값을 P4로 보내라

5. P2의 값을 P5로 보내라

라고 조금 더 쉽게 생각 할 수 있다.

 

2)

우리는 결과를 알고 있고 D의 리스트를 알고 있으니 역추적이 가능하다

즉 1) 의 결과를 반대로

S1을 D1의 값 4 -> P4로

S2를 D2의 값 3 -> P3으로

....

 

를 진행한다

 

3) 리스트를 출력한다

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n, k = map(int, input().split())

s = list(map(int, input().split()))
d = list(map(int, input().split()))

p = [0 for _ in range(n)]


for _ in range(k):
    for j in range(n):
        p[d[j]-1] = s[j]
    s = list(p)


print(*p)

---

• 얻어갈 부분

1. 구현은 금방 했으나 s = p 로 메모리를 참조해버려서 중간에 배열이 꼬였다. 리스트를 복사할 때는 list()로 묶어서 복사하자