백준 2164번 파이썬

iillyy·2021년 3월 12일
0

알고리즘

목록 보기
7/13
post-thumbnail


이 문제는 큐의 원리와 덱 함수를 사용하면 쉽게 풀 수 있는 문제였습니다.
맨 위에 있는 숫자를 없애고 그 아래에 있던 숫자를 리스트의 맨 아래로 보내는
과정을 반복하고 리스트에 한 글자만 남았을 때의 숫자를 맞추면 되는 문제입니다.

from collections import deque

case = int(input())
card=[]

for i in list(range(1,case+1)):
    card.append(i)
    dq = deque(card)
    for j in range(len(dq)):
        dq.popleft()
        dq.rotate(-1)
        if len(dq) == 1:
            break
print(dq)

처음에는 입력한 값만큼 for문을 돌리고 1부터 입력한 값까지 리스트를 만듭니다.
그리고 그 리스트를 덱 리스트로 만든 후 리스트 맨 왼쪽의 값을 꺼내는 popleft()함수를
써서 맨 위의 값을 제거하고 리스트를 왼쪽으로 움직여 dq[0] 의 값을 dq[-1] 바꾸는 함수
rotate(-1) 함수를 썼습니다.

그런데 이 답안지를 제출하고 나서는 시간 초과가 뜨더라고요 ㅜ

그래서 구글을 참고하여 고쳐보았는데

import collections
from collections import deque


dq = collections.deque(i for i in range(case)) # case만큼 리스트를 만들어주는 함수


while len(dq) > 1:
    dq.popleft()
    dq.rotate(-1)

print(dq[0]+1)

이렇게 고쳤을 때에는 시간 초과가 나지 않았습니다.
아마 처음 포문을 돌릴 때 값을 다 리스트에 넣는 방식으로 하여 시간초과가 뜬 것 같습니다.
collections.deque 함수를 이용하고
(i for i in range(case)) 로 list.append() 를 대체하였습니다.

0개의 댓글