백준 2164번 카드2

백준 2164번 카드2 문제이다. 

 

문제를 보면 

 

문제만 보면 리스트를 반복문을 통해 요소를 삭제하고 맨뒤로 돌리고 반복해주면 쉽게 풀릴 것으로 보였다.

코드를 작성하고 제출을 했지만... 시간초과가 나왔다.

 

크게 시간복잡도가 큰게 없다고 생각해서 찾아보니 리스트의 del, insert와 같은 함수들은 시간 복잡도가 O(n)이라고 한다.

deque를 이용하면 시간복잡도를 O(1)로 줄일 수 있다고 한다. 

 

코드를 보면 

import sys
from collections import deque

deq = deque()

n = int(sys.stdin.readline().strip())
for i in range(n):
    deq.append(i)

while True:
    if len(deq) == 1:
        break
    deq.popleft()
    deq.append(deq.popleft())
print(deq[0]+1)

deque에는 popleft() 라는 함수가 있어 0번째 요소를 삭제하고 반환도 해주기 때문에 코드가 1줄 더 줄었다. 

 

리스트를 이용해 요소의 추가 삭제가 빈번하게 구현된 것이 시간초과가 나온다면 deque를 이용하면 좋을것 같다. 

 

성공!