(Python)백준 코딩테스트 연습 - 카드2(2164)

1. 문제

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

2164번: 카드2

2. 풀이

from collections import deque
import sys

# n : 카드 개수
n = int(sys.stdin.readline())

# n_l : 카드들을 저장할 리스트
n_l = deque([i for i in range(1, n+1)])

while True:
    # 카드가 한개만 남은 경우 반복 종료
    if len(n_l) == 1:
        break
    # 카드 중 멘 위의 카드를 제거
    n_l.popleft()
    
    # 카드 중 맨 위에 있는 카드를 맨 아래로 이동
    n_l.append(n_l.popleft())


# 마지막에 남은 카드를 출력
print(n_l[0])

3. 후기

 - 문제를 보고 먼저 들었던 풀이 방법은 리스트를 사용해서 해결하는 방법이다. 해당 방법을 사용하여 제출했을 때는 시간 초과가 나왔다. 리스트 자료 형태는 pop()을 하게될 시에 O(N)의 시간 복잡도를 갖기 때문에 시간 초과가 나올 수밖에 없고, queue의 형태로 시간 복잡도를 줄이기 위해서는 collections 라이브러리가 제공하는 deque를 사용해야 했다. 이후에 queue 형태의 자료형을 사용할 때는 시간 복잡도를 줄이기 위해 꼭 collections의 deque를 사용해야겠다.