20923(숫자 할리갈리 게임) - 시간 초과(pypy 해결)

숫자 할리갈리 게임

 

문제

인간이 가장 심심함을 느낀다는 오후 1시 22분, 도도와 수연이는 숫자 할리 갈리 게임을 하려 한다. 숫자 할리 갈리 게임의 규칙은 다음과 같다.

[숫자 할리 갈리 게임의 규칙]

1. 초기에 도도와 수연이는 각각 N장의 카드로 이루어진 덱을 배분받는다. 게임 시작 시 그라운드는 비어있는 상태이다. 
   • 덱은 숫자가 보이지 않게 카드를 뒤집어 쌓아 놓은 카드 더미를 의미한다. 도도와 수연이는 자신의 덱을 가지고 게임을 진행하게 된다.
   • 그라운드는 도도와 수연이가 게임을 진행하며 자신이 가진 덱에서 가장 위에 있는 카드를 내려놓게 되는 땅을 의미한다. 그라운드에 카드를 내려놓을 때는 자신의 그라운드에 카드를 내려놓으며, 그라운드에 카드 더미가 존재할 경우 기존에 만들어진 카드 더미 위로 카드를 내려놓는 방식으로 진행한다.
2. 도도를 시작으로 도도와 수연이가 차례대로 그라운드에 자신이 가진 덱에서 가장 위에 위치한 카드를 그라운드에 숫자가 보이도록 내려놓는다.
3. 종을 먼저 치는 사람이 그라운드에 나와 있는 카드 더미를 모두 가져갈 수 있다. 종을 칠 수 있는 조건은 다음과 같다.
   • 그라운드에 나와 있는 각각의 카드 더미에서 가장 위에 위치한 카드의 숫자 합이 5가 되는 순간 수연이가 종을 친다. 단, 어느 쪽의 그라운드도 비어있으면 안된다.
   • 그라운드에 나와 있는 각각의 카드 더미에서 가장 위에 위치한 카드의 숫자가 5가 나오는 순간 도도가 종을 친다.
4. 종을 쳤다면, 상대방의 그라운드에 있는 카드 더미를 뒤집어 자신의 덱 아래로 그대로 합친 후 자신의 그라운드에 있는 카드 더미 역시 뒤집어 자신의 덱 아래로 그대로 가져와 합친다.
   • 종을 쳐서 그라운드에 있는 카드 더미를 가져가는 행위는 게임의 진행 순서에 영향을 미치지 않는다.

   

5.  M번 진행한 후 자신의 덱에 더 많은 카드를 지닌 사람이 승리하고 M번 진행 후 각자의 덱에 있는 카드의 개수가 같다면 비긴 것으로 본다. 게임 진행 도중 자신의 덱에 있는 카드의 수가 0개가 되는 즉시 상대방이 승리한 것으로 본다. (둘 중 한 명이 2~4번까지의 과정을 진행하는 것을 1번 진행한 것으로 본다.)

게임을 M번 진행한 후 승리한 사람은 누구일까?

입력

첫째 줄에는 도도와 수연이가 가지는 카드의 개수 N(1≤N≤30000)과 게임 진행 횟수 M(1≤M≤2500000)이 주어진다.

둘째 줄부터 N$N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연이가 가진 덱의 맨 아래에 위치한 카드에 적혀 있는 수부터 맨 위에 위치한 카드에 적힌 수까지 차례대로 주어진다. (각각의 카드는 1 이상 5 이하의 자연수가 적혀있다.)

 

출력

게임을 이긴 사람이 도도라면 do를 출력하고 게임을 이긴 사람이 수연이라면 su를 출력한다. 비겼을 경우, dosu를 출력한다.

---

처음에는 deque로 안했는데 역시나 시간 초과.

deque로 바꾸었는데 그래도 시간 초과... pypy로 했더니 통과는 하였다.

 

import sys

N, M = map(int,sys.stdin.readline().split())
from collections import deque

do_cards = deque()
su_cards = deque()
for _ in range(N):
    A, B = map(int,sys.stdin.readline().split())
    do_cards.append(A)
    su_cards.append(B)

do_ground = deque()
su_ground = deque()

while M > 0:
    # 도 부터 시작
    A = do_cards.pop()
    do_ground.append(A)
    # 횟수 줄이기
    M -= 1
    # do의 카드 덱이 비면
    if len(do_cards) == 0:
        break
    # 도가 이기는 경우
    if A == 5:
        do_cards.extendleft(su_ground)
        do_cards.extendleft(do_ground)
        do_ground = deque()
        su_ground = deque()
    # 수가 이기는 경우
    if do_ground and su_ground:
        if do_ground[-1] + su_ground[-1] == 5:
            su_cards.extendleft(do_ground)
            su_cards.extendleft(su_ground)
            do_ground = deque()
            su_ground = deque()
    # 횟수가 끝날 때.
    if M == 0:
        break
    # 수 확인.
    B = su_cards.pop()
    su_ground.append(B)
    M -= 1
    if len(su_cards) == 0:
        break
    if B == 5:
        do_cards.extendleft(su_ground)
        do_cards.extendleft(do_ground)
        do_ground = deque()
        su_ground = deque()
    if do_ground and su_ground:
        if do_ground[-1] + su_ground[-1] == 5:
            su_cards.extendleft(do_ground)
            su_cards.extendleft(su_ground)
            do_ground = deque()
            su_ground = deque()

if len(do_cards) > len(su_cards):
    print('do')
elif len(do_cards) < len(su_cards):
    print('su')
else:
    print('dosu')