[백준] 18258번 - 카드2

1. 문제 요약

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

 

1부터 N까지 카드가 순서대로 쌓여있다.

다음 과정을 반복한다:

1. 맨 위 카드 버리기
2. 그 다음 카드 맨 아래로 이동

→  마지막에 남는 카드 번호를 구하는 문제

---

2. 예시로 이해하기

N = 6일 때

123456
→ 1 버림: 23456
→ 2 아래로: 34562
→ 3 버림: 4562
→ 4 아래로: 5624
→ 5 버림: 624
→ 6 아래로: 246
→ 2 버림: 46
→ 4 아래로: 64
→ 6 버림: 4

 

→ 정답: 4

---

3. 접근 방법

이 문제는 가장 아래있는 수를 제어해야 하므로 큐 문제

핵심 연산

• 앞에서 제거 → popleft()
• 뒤에 추가 → append()

→ deque 사용 필수

---

4. 내가 작성한 코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
queue = deque([i for i in range(1, n+1)])

while queue:
    if len(queue) == 1:
        print(queue[0])
        break
    queue.popleft()
    queue.append(queue.popleft())

 

---

5. 코드 동작 분석

 1) 큐 초기화

 

queue = deque([1, 2, 3, ..., n])

---

 2) 반복 로직

 

queue.popleft() # 카드 버리기
queue.append(queue.popleft()) # 다음 카드 뒤로 보내기

 

---

 3) 종료 조건

 

if len(queue) == 1:

---

5. 시간 복잡도

• 각 연산 → O(1)
• 총 반복 → N번

→ O(N)

N ≤ 500,000 → 충분히 통과