백준 2164 큐, deque 연습

[문제 링크] 🔗 백준 2164 - 카드2

백준 2164 큐(deque) 문제풀이

 

백준 2164 문제는 큐(Queue) 자료구조를 활용하여 풀 수 있는 문제이며,

카드를 특정 규칙에 따라 제거하면서 마지막에 남는 카드를 찾는 문제이다.

 

📌 문제 이해

1. 1 ~ N까지의 카드가 순서대로 놓여 있다.
2. 맨 위의 카드를 버린다.
3. 그다음 맨 위의 카드를 제일 아래로 옮긴다.
4. 위 과정을 반복하여 마지막에 남는 카드를 찾는다.

✅ 큐(Queue)의 FIFO(선입선출) 구조를 활용해야 한다.

✅ deque를 사용하면 더 효율적으로 해결할 수 있다.

 

📌 풀이 방법

 

이 문제를 해결하는 방법은 두 가지가 있다.

1. deque.rotate() 메서드를 사용하는 방법
2. popleft()와 append()를 조합하여 직접 구현하는 방법

🔹 1. rotate() 메서드를 이용한 풀이

 

✅ rotate(-1)을 사용하면 큐의 맨 앞 요소를 맨 뒤로 이동할 수 있다.

import sys
from collections import deque
N = int(sys.stdin.readline().rstrip())
lst = deque([i+1 for i in range(N)])
#print(lst)
while True:    
    if len(lst) == 1:
        break    
    lst.popleft()    # 맨 위 카드 버리기
    lst.rotate(-1)   # 맨 위 카드를 아래로 이동

print(lst[0])

 

🔹 실행 예제

입력  
6  

출력  
4

 

🔹 2. popleft()와 append()를 이용한 풀이

 

✅ popleft()로 맨 위 카드를 빼고, 다음 카드를 append()로 뒤로 보낸다.

import sys
from collections import deque
N = int(sys.stdin.readline().rstrip())
lst = deque([i+1 for i in range(N)])
#print(lst)
while True:    
    if len(lst) == 1:
        break    
    lst.popleft()    # 맨 위 카드 버리기 
    lst.append(lst.popleft()) # 다음 카드 뒤로 이동

print(lst[0])

 

🔹 실행 예제

입력  
6  

출력  
4

 

📌 두 가지 방법 비교

방법	코드 간결성	실행 속도
rotate() 사용	✅ 간결함	🚀 빠름
popleft() + append() 사용	✅ 직관적	🚀 빠름

💡 둘 다 시간 복잡도는 O(N), 속도 차이는 거의 없다.

💡 개인적으로 rotate() 방법이 간결하여 추천한다!

 

📌 정리

✅ deque.popleft()를 사용하여 맨 위의 카드를 제거할 수 있다.

✅ deque.rotate(-1)을 사용하면 카드를 아래로 보낼 수 있다.

✅ popleft() + append() 조합을 사용하여 직접 구현할 수도 있다.

✅ 큐(Queue) 개념을 익히기에 좋은 연습 문제이다.