2164: 카드2 - Python

문제

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

풀이 1 (오답: 시간초과)

# 풀이 1 - 시간초과

N = int(input())
arr = list(range(1, N+1))
while True:
    if len(arr) == 1:
        print(arr[0]) 
        break
    arr.pop(0)
    arr.append(arr.pop(0))

• 시간 초과가 발생했는데, 그 이유는...!
  arr.pop(0)을 수행할 때, 즉 리스트의 첫 번째 요소를 제거할 때 나머지 모든 요소를 한 칸씩 앞으로 이동하여야 하며, 이에 O(n)의 시간 복잡도를 갖는다.
  
• 따라서 양쪽 끝에서의 삽입, 삭제 연산이 O(1)의 시간 복잡도를 갖는collections.deque 모듈을 사용하는 것이 좋다.
• 추가적으로,Queue는 멀티쓰레드 환경을 지원하기 때문에 deque보다 더 느리다.
  -> 결론: deque을 사용하자.

풀이 2 (정답)

from collections import deque

N = int(input())
dq = deque(range(1, N+1))

while True:
    if len(dq) == 1:
        print(dq[0])
        break
    dq.popleft()
    dq.rotate(-1)

이를 다음과 같이 가독성 좋게 고칠 수 있다.

from collections import deque

N = int(input())
dq = deque(range(1, N+1))

while len(dq) > 1:
    dq.popleft()
    dq.rotate(-1)

print(dq[0])

---

오늘의 교훈

• deque은 빠르다. deque을 사랑하자.
• 다음은 deque의 사용 예제이다. (출처: GPT)

# import
from collections import deque

# 덱 생성
dq = deque()

# 오른쪽 끝에 요소 추가
dq.append(10)      # dq: deque([10])
dq.append(20)      # dq: deque([10, 20])

# 왼쪽 끝에 요소 추가
dq.appendleft(5)   # dq: deque([5, 10, 20])

# 오른쪽 끝에서 요소 제거
right = dq.pop()   # right: 20, dq: deque([5, 10])

# 왼쪽 끝에서 요소 제거
left = dq.popleft() # left: 5, dq: deque([10])

# 반복 가능한 객체의 요소들을 오른쪽 끝에 추가
dq.extend([30, 40, 50])  # dq: deque([10, 30, 40, 50])

# 반복 가능한 객체의 요소들을 왼쪽 끝에 추가
dq.extendleft([1, 2, 3]) # dq: deque([3, 2, 1, 10, 30, 40, 50])

# 덱 회전 (오른쪽으로 2칸)
dq.rotate(2)       # dq: deque([40, 50, 3, 2, 1, 10, 30])

# 덱 회전 (왼쪽으로 3칸)
dq.rotate(-3)      # dq: deque([2, 1, 10, 30, 40, 50, 3])

참고 자료

• [Python] 리스트 주요 연산 시간 복잡도
  
• collections — Container datatypes
• [Python] 파이썬 Queue와 deque 속도