[Python/파이썬] 백준 29813번 최애의 팀원

29813번: 최애의 팀원

 

코드

from collections import deque

n = int(input())
students = deque([list(input().split()) for _ in range(n)])

while len(students) > 1:
    init, num = students.popleft()
    for _ in range(int(num)-1):
        students.append(students.popleft())
    students.popleft()

print(students[0][0])

 

배열의 양쪽에서 입출력이 가능한 큐를 사용해서 문제를 풀면 된다.

 

파이썬에서는 deque 대신 그냥 리스트를 사용해도 할 수 있지만, 리스트의 가장 앞 원소를 pop하는 것은 O(n)의 시간복잡도를 가지는데, deque는 O(1)이므로 deque를 사용하는 것이 빠르다. 이는 deque가 double-linked list로 구현되어 있기 때문이다.