[백준] 2164. 카드2 / python 파이썬

🚩 큐(queue)

 

thinking

포인트는  deque 모듈 을 사용하는 것이다!!!!!

그냥 pop(0)으로 풀면 시간초과 남

---

deque 사용하는 이유 : popleft의 시간차이 때문에

list의 경우 pop()으로 마지막 값을 꺼내는 경우 O(1) (일정한 시간) 시간이 걸리는데, pop(0)으로 가장 앞단에 값을 꺼낼때는 list 크기에 따라 읽어 오는 시간이 달라져 O(n) 시간이 걸림.

하지만 deque를 사용할 경우에, popleft()를 사용하면 리스트의 pop(0)과 같은 기능을 주면서 걸리는 시간은 O(1)이 걸린다.

 

코드 (pass)

from collections import deque

N = int(input())
queue = deque()

for i in range(1, N+1):
    queue.append(i)

while len(queue) > 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue.pop())

 

시간초과 난 코드 (fail)

N = int(input())
queue = [i for i in range(1, N+1)]  # 1~N 까지 카드 리스트 만들기

while True:  # 일단 계속 돌리다가
    if len(queue) == 1:  # 카드 한장 남으면 반복문 종료
        break

    queue.pop(0)  # 맨 앞 카드 한번 빼주고
    queue.append(queue.pop(0))  # 두번째 카드 (그 다음 맨 앞 카드) 빼서 리스트 맨 뒤에 넣기

print(*queue)

 

 

한줄후기

큐랑 deque랑 여태 같은 건줄 😆