[baekjoon] 백준 2164번(파이썬): 카드2

문제

2164번: 카드2

알고리즘

- deque() 함수를 통해 문제를 수행한다.

- n장의 카드를 1부터 n까지 번호를 매겨준다.

- 리스트의 크기가 1일때까지 반복하여 카드를 하나 버리고 첫 번째 카드를 맨 뒤로 옮겨준다.

코드

import sys
from collections import deque

n = int(sys.stdin.readline())
heap = deque()

# n장의 카드를 1 부터 n 까지 번호르 매겨준다.
for i in range(1, n + 1):
    heap.append(i)

# 리스트의 크기가 1일때까지 반복한다.
while len(heap) != 1:
    heap.popleft() # 팝한다.
    heap.append(heap.popleft()) # 첫 번째 수를 맨 뒤로 옮긴다.

print(heap[0])

 

실패한 코드(시간초과)

import sys

n = int(sys.stdin.readline())

heap = [i for i in range(1, n + 1)]

while len(heap) != 1:
    heap.pop(0)
    heap.append(heap.pop(0))

print(heap[0])

pop(i)는 시간 복잡도가 O(N)이기 때문에 위 코드의 시간 복잡도는 O(N^2)이 된다.

따라서 deque 모듈을 통해 시간복잡도가 O(1)인 popleft() 함수를 사용하여 코드의 시간 복잡도를 O(N)으로 만들어 문제를 풀었다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법