[BOJ/백준] 20923 숫자 할리갈리 게임 - 파이썬

문제설명

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

20923번: 숫자 할리갈리 게임

게임의 규칙은 흔히 알고 있는 할리갈리 게임의 규칙과 유사하다. 

게임을 m번 반복했을 때 카드를 더 많이 가지고 있는 사람을 출력하는 문제

 

문제풀이

처음에는 도도와 수연이의 카드 덱과 그라운드 덱을 각각 2개씩 따로 만들어 풀었었는데,

if 문의 조건도 복잡해지고 while문을 남발해서 시간초과가 났다

 

시간초과 문제를 해결 못해서 결국 출제진 분이 올려주신 해설 코드를 참고하였다

https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=pasdfq&logNo=222251572937&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

기본적인 아이디어는 비슷하나, 카드 덱과 그라운드 덱을 2차원으로 만들어서 인덱스를 활용해 훨씬 간단하게 풀 수 있었다

특히, 덱을 합치기 위해 작성한 for문을 보고 우와! 했다..

 

코드

시간초과 났던 코드

import sys
from collections import deque

n,m=map(int,input().split())
do,su=deque([]),deque([])

for i in range(n):
    a,b=map(int,input().split())
    do.append(a)
    su.append(b)
    
tmp1,tmp2=deque([]),deque([])
for i in range(m):
    if i%2==0: #do가 먼저
        tmp1.append(do.pop())
    else:
        tmp2.append(su.pop())
    if (tmp1 and tmp1[-1]==5) or (tmp2 and tmp2[-1]==5):##do가 종
        while(tmp2):
            do.appendleft(tmp2.popleft())
        while(tmp1):
            do.appendleft(tmp1.popleft())
    elif tmp1+tmp2==5 and tmp1 and tmp2:
        while(tmp1):
            su.appendleft(tmp1.popleft())
        while(tmp2):
            su.appendleft(tmp2.popleft())
    if len(do)==0:
        break
    elif len(su)==0:
        break

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

통과한 코드

import sys
from collections import deque

n,m=map(int,input().split())
start=[deque(), deque()]
temp=[deque(),deque()]

for i in range(n):
    a,b=map(int,input().split())
    start[0].appendleft(a)
    start[1].appendleft(b)

t=0
for _ in range(m):
    temp[t].appendleft(start[t].popleft())
    if not start[t]:##둘 중 하나라도 0이 되면
        break
    win=-1
    for i in [0,1]:
        if temp[i] and temp[i][0]==5: # 둘중 하나가 5
            win=0
    if temp[0] and temp[1] and temp[0][0]+temp[1][0]==5: 
            win=1
    if win!=-1:##종 치지 않을 경우 pass
        for i in [1-win,win]: ##누구 카드를 먼저 가져오는지
            while temp[i]:
                start[win].append(temp[i].pop())
    t=1-t

if len(start[0])>len(start[1]):
    print('do')
elif len(start[1])>len(start[0]):
    print('su')
else:
    print('dosu')

 

어려웠던 점/느낀 점

파이썬 내장함수들의 시간복잡도를 잘 알아봐야겠다.. 시간초과 안나도록 더 효율적으로 코드 짜기..!