경험치가 늘 부족한 학생

Updated:

1. 문제 이해 하기

플레이어, 카드, P, S가 동일한 숫자(0,1,2 등 양의 정수)를 사용하기 때문에 자칫 잘못하다가 문제를 잘못 이해할 수 있다.

예제 입력 1을 통해 어떤 방식으로 해답을 구해야하는지 살펴보고 코드를 살펴보도록 하겠다.

[조건]
* 플레이어: 0,1,2
* 카드: 0 ~ N-1
* P: 0,1,2 숫자 중 하나
* S: 0 ~ N-1

[예제 입력 1번]
3
2 0 1
1 2 0

[예제 출력 1번]
2

일단 각 숫자들을 살펴보자. 플레이어도 (0,1,2) 카드도 (0,1,2) P,S도 (0,1,2) 이기 때문에 헷갈리기 아주 쉽다. 문제에서 설명한 방식대로 예제 출력 1번이 어떻게 나오는 지 살펴보겠다.

카드 0 1 2
P   2 0 1
S   1 2 0

P는 각 카드가 어떤 플레이어에게 도착해야하는지 나타낸다. 따라서 예제 1번에서 카드 0이 플레이어 2에게, 카드 1이 플레이어 0에게, 카드 2가 플레이어 1에게 도착해야한다. (플레이어 0은 카드 1을, 플레이어 1는 카드 2를, 플레이어 2는 카드 0을 받아야한다.)

S는 카드를 섞는 방식을 뜻한다. 예제 1번에서는 0 위치의 카드가 1 위치로, 1 위치의 카드가 2위치로, 2위치의 카드가 0위치로 섞인다.

1번째 섞었을 때

카드 2 0 1

보통 여기서 많이 헷갈린다. 카드가 (2, 0, 1)이 되어 P와 동일하기 때문에 정답이 1이 아닐까라고 생각하게 된다. 하지만 P[i]는 맨처음 i번째 위치에 있던 카드가 최종적으로 어느 플레이어에 도달해야하는 지를 나타내는 것이기 때문에 카드 순서를 나타내지않는다. 정답과 비교해보면 그 차이를 쉽게 확인할 수 있다.

1번째 섞었을 때

카드 2 0 1
정답 1 2 0

2번째 석었을 때 카드 순서가 정답과 일치하게 된다.

2번째 섞었을 때

카드 1 2 0
정답 1 2 0

2. 코드

풀이 방법 (1)

  1. 각 플레이어별로 어떤 카드가 도착해야하는지 set에 담아놓는다.(정답 구하기)
  2. while문을 이용해 카드를 섞는 시뮬레이션을 구현
    • 현재 카드 순서로 각 플레이어에게 카드를 나눠준다.
      • 카드가 올바르게 모두 도착한 경우 종료.
      • 이미 한 번 나왔던 카드 순서면 더이상 섞어도 섞어도 플레이어에게 줄 수 없기 때문에 종료 후 -1 출력
    • 카드를 다시 섞는다.

코드 (1)

import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

n = int(input())
P = list(map(int,input().split()))
S = list(map(int,input().split()))

answer = defaultdict(set)
visited = set()

for i in range(n):
    answer[P[i]].add(i)

cnt = 0
cards = list(range(n))
while True:
    first,second,third = set(cards[0:n:3]), set(cards[1:n:3]), set(cards[2:n:3])
    if first == answer[0] and second == answer[1] and third == answer[2]:
        break
    if tuple(cards) in visited:
        cnt = -1
        break
    visited.add(tuple(cards))
    temp = [0] * n
    for i in range(n):
        temp[S[i]] = cards[i]
    cards = temp
    cnt += 1
print(cnt)

일단 이 코드가 통과하긴했지만 주의해야할 부분이 몇가지 존재했다.

  1. 이미 나왔던 카드 순서인지 확인하기 위해 카드 순서를 tuple로 변경한 후 visited에 저장한다.
    • tuple을 계속해서 저장하기 때문에 메모리가 많이 필요하다.
  2. 카드 분배할 때 list를 set으로 변경하는 과정
  3. 정답인지 아닌지 확인하기 위해 set과 set을 비교하는 과정

이미 나왔던 카드 순서인지 아닌지 확인하기 위해 set을 이용해 비교하는 방법말고 다른 방법을 찾아보았다.

풀이 방법 (2)

일단 먼저 발상을 전환해보았다. 카드를 플레이어에게 올바르게 분배하는 방법을 찾는 것보다 플레이어를 카드에 올바르게 분배하는 방법을 찾는 것이 더 쉬울 수 있다는 생각이 들었다.

예시를 살펴보자. P는 각 카드가 어떤 플레이어에게 도달해야하는지 표시한 배열이다. 하지만 우리는 플레이어를 카드에 올바르게 분배하는 방법을 찾을 것이기 때문에 각 카드가 0 ~ N-1를 표시하는 것이 아닌 어떤 플레이어에 도착해야하는 지 적혀있다고 생각할 것이다. 따라서 P는 이제부터 어떤 플레이어에 도착해야하는 지 적혀있는 카드의 현재 순서라고 보면 된다.

P 예제

1 1 2 0 2 0 1 0 2 2 1 0

이렇게 생각했을 때 정답의 각 카드는 다음과 같이 숫자를 지니고 있어야한다.

정답

0 1 2 0 1 2 0 1 2 0 1 2

이제 P를 이용해 답을 구하면 된다.

  • 이미 나왔던 카드 순서인지 확인하기 위해 각 순서를 문자열로 변환하여 visited set에 있는지 체크하였다.
    • tuple을 사용할 때보다 메모리 사용량이 적었다.
  • 정답도 '012'로 구성된 문자열로 구성하여 문자열끼리 비교하는 방식을 사용하였다.

코드 (2)

import sys
def input(): return sys.stdin.readline().rstrip()

n = int(input())
P = input().split()
S = list(map(int,input().split()))

visited = set()
answer,cnt = '012' * (n//3), 0
while True:
    seq = "".join(P)
    if seq == answer:
        break
    if seq in visited:
        cnt = -1
        break
    visited.add(seq)
    temp = [0] * n
    for i in range(n):
        temp[S[i]] = P[i]
    P = temp
    cnt += 1
print(cnt)

Leave a comment

You may also enjoy