(Python) 백준 2164번 카드2

 

파이썬에 적응하는 중인데, 아직 파이썬의 자료구조 활용에 많이 서툴다. 이 문제에서 List를 사용해 Queue를 구현해 풀었다가 시간초과를 만나버렸다. 

 

초기 코드

n = int(input())
cards = [ i+1 for i in range(n)]

while len(cards)>1:
    cards.pop(0)
    if len(cards) == 1: break
    cards.append(cards.pop(0))

print(cards[0])

 

정답 코드

from collections import deque

n = int(input())
cards = deque([i+1 for i in range(n)])

while len(cards)>1:
    cards.popleft()
    if len(cards) == 1: break
    cards.append(cards.popleft())

print(cards[0])

 

List 자료형의 pop(0) 연산의 시간복잡도가 O(N)이라 발생하는 시간초과였다. Python은 각 자료구조를 구현하는 방식이 좀 더 다양한 것 같아, 각각의 시간복잡도를 주의해서 사용해야겠다.

 

2024.07.20 - [분류 전체보기] - Python으로 Queue 사용하기