처음 코드를 쓰고 실행했는데 에러가 없었다. 결과는 틀렸는데 에러가 없으니 더 찾기 어려웠다.
N장의 카드가 위에서부터 1번, 2번, …, N번 순서로 놓여 있다. 다음 동작을 카드가 1장 남을 때까지 반복한다.
- 맨 위 카드를 바닥에 버린다.
- 그 다음 맨 위 카드를 맨 아래로 옮긴다.
마지막에 남은 카드 번호를 출력한다.
| 항목 | 내용 |
|---|---|
| 문제 번호 | 백준 2164 |
| 난이도 | 실버 4 |
| 분류 | 자료구조, 큐 |
| 핵심 자료구조 | collections.deque |
| 핵심 연산 | popleft() — 앞에서 꺼내기, append() — 뒤에 추가 |
| 입력 범위 | 1 ≤ N ≤ 500,000 |
예제
| N | 답 |
|---|---|
| 6 | 4 |
| 4 | 4 |
| 7 | 6 |
| 1 | 1 |
처음 작성한 코드 — 버그 4곳
n = int(input())
list = []
for i in range(n): # 버그 ④ — 0부터 시작
list.append(i)
card = deque(list) # 버그 ① — import 없음
for _ in range(n-1):
card.popleft # 버그 ② — 괄호 없음
card.append(card.appendleft) # 버그 ③ — 메서드 이름 틀림
print(card.pop6) # 버그 ② 반복 + 오타↑ ②③은 파이썬이 에러를 내지 않아서 실행은 됐다. 결과만 이상했다.
버그 분석
버그 ① — import가 없다
deque는 파이썬 내장 타입이 아니다. collections 모듈에서 명시적으로 가져와야 한다.
# 틀림
card = deque(list)
# 맞음
from collections import deque
card = deque(list)| 구분 | 내용 |
|---|---|
list, dict, set |
파이썬 내장 타입 — import 불필요 |
deque, Counter, defaultdict |
collections 모듈 — import 필요 |
버그 ② — 괄호 없이 쓴 메서드
두 줄에서 발생했다.
card.popleft # 실행 안 됨
print(card.pop6) # AttributeError (오타 + 괄호 없음)파이썬에서 함수와 메서드는 일급 객체(first-class object)다. 이름만 쓰면 그 객체를 "가리키는" 것이고, ()를 붙여야 "호출"이 된다.
f = card.popleft # f는 popleft 메서드 자체를 가리킴 (실행 안 됨)
f() # 이렇게 해야 실행됨
card.popleft() # 한 줄로 쓰면 이렇게| 코드 | 파이썬이 하는 일 | 실제 실행 |
|---|---|---|
card.popleft |
메서드 객체를 참조 (아무것도 안 함) | ❌ |
card.popleft() |
메서드를 호출 | ✅ |
card.pop6 |
pop6이라는 속성/메서드 없음 |
❌ AttributeError |
card.pop() |
맨 뒤 원소를 꺼내 반환 | ✅ |
파이썬은
card.popleft처럼 괄호 없이 메서드를 참조해도 에러를 내지 않는다. 그냥 아무것도 안 할 뿐이다. 결과가 이상해도 에러 메시지가 없어서 원인을 찾기 어렵다.버그 ③ — appendleft가 아니라 popleft
card.append(card.appendleft) # 틀림
card.append(card.popleft()) # 맞음이 줄이 하려는 동작: 맨 위 카드를 꺼내서 맨 아래로 이동.
deque의 메서드를 방향과 동작으로 정리하면 다음과 같다.
| 메서드 | 동작 | 위치 | 이 문제에서 |
|---|---|---|---|
popleft() |
꺼냄 | 왼쪽(앞) | ✅ 맨 위 카드 꺼낼 때 |
pop() |
꺼냄 | 오른쪽(뒤) | ✅ 최종 결과 출력 시 |
append(x) |
추가 | 오른쪽(뒤) | ✅ 카드를 맨 아래로 |
appendleft(x) |
추가 | 왼쪽(앞) | ❌ 이 문제에선 사용 안 함 |
"맨 위 카드를 꺼내서 맨 아래로"를 코드로 쓰면:
꺼낸_카드 = card.popleft() # 앞에서 꺼냄
card.append(꺼낸_카드) # 뒤에 추가
# 한 줄로 줄이면
card.append(card.popleft()) # popleft()의 반환값을 append에 바로 전달appendleft를 쓰면 꺼낸 카드를 다시 앞에 붙이므로 순서가 전혀 바뀌지 않는다.
버그 ④ — range(n)은 0부터 시작한다
for i in range(n): # i = 0, 1, 2, ..., n-1
for i in range(1, n+1): # i = 1, 2, 3, ..., n문제의 카드는 1번부터 N번까지다. range(n)으로 만들면 0번 카드부터 시작하여 번호가 전부 1씩 어긋난다.
| 코드 | n=6일 때 생성되는 리스트 | 문제 조건 (1~N) |
|---|---|---|
range(n) |
[0, 1, 2, 3, 4, 5] | ❌ 0번 카드가 존재 |
range(1, n+1) |
[1, 2, 3, 4, 5, 6] | ✅ |
수정된 코드 — BEFORE / AFTER
| BEFORE — 버그 있는 코드 | AFTER — 수정된 코드 |
|---|---|
|
|
| 위치 | BEFORE | AFTER | 이유 |
|---|---|---|---|
| 1번째 줄 | (없음) | from collections import deque |
deque 사용 전 import 필요 |
| 카드 초기화 | range(n) |
range(1, n+1) |
카드 번호 1~N |
| 첫 번째 연산 | card.popleft |
card.popleft() |
괄호 없으면 실행 안 됨 |
| 두 번째 연산 | card.appendleft |
card.popleft() |
앞에서 꺼내서 뒤에 붙여야 함 |
| 출력 | card.pop6 |
card.pop() |
오타 + 괄호 수정 |
알고리즘 동작 시뮬레이션 — n = 6
초기 상태: deque([1, 2, 3, 4, 5, 6])
| 반복 | ① 버리는 카드 (popleft) | ② 뒤로 이동 (append(popleft())) | 이후 deque 상태 |
|---|---|---|---|
| 1회차 | 1 | 2 | [3, 4, 5, 6, 2] |
| 2회차 | 3 | 4 | [5, 6, 2, 4] |
| 3회차 | 5 | 6 | [2, 4, 6] |
| 4회차 | 2 | 4 | [6, 4] |
| 5회차 | 6 | 4 | [4] |
| 종료 | 카드 1장 남음 | → 답: 4 | |
n장 카드에서 1장을 남기려면 (n - 1)번 반복이 필요하다.
# 카드 수 변화 (n=6)
6장 → 4장 → 3장 → 2장 → 1장
# 반복 횟수: 5 = n - 1한 번의 반복에서 버린 카드 1장, 뒤로 이동한 카드 1장이 처리된다. 이동한 카드는 다음 라운드에서 다시 등장한다. n - 1번 반복 후 정확히 1장이 남는다.
for 버전 vs while 버전
| for 버전 (완성 코드) | while 버전 (간결한 버전) |
|---|---|
|
|
| 항목 | for 버전 | while 버전 |
|---|---|---|
| 초기화 | list 생성 후 deque 변환 | deque(range(1, n+1)) 한 줄 |
| 종료 조건 | range(n-1) — 횟수 기반 |
len(card) > 1 — 상태 기반 |
| 의미 전달 | "n-1번 반복" | "카드 1장 남을 때까지" |
| 코드 길이 | 더 길다 | 더 짧다 |
while 버전에서 deque(range(1, n+1))는 range 객체를 deque 생성자에 직접 넘긴다. list로 변환할 필요 없다.
왜 list가 아니라 deque인가
이 문제의 핵심 연산은 앞에서 꺼내기다. list와 deque의 앞 원소 제거 비용이 다르다.
# list.pop(0) — O(n)
lst = [1, 2, 3, 4, 5, 6]
lst.pop(0)
# 내부에서 나머지 원소를 전부 한 칸씩 앞으로 이동
# → 원소 수만큼 메모리 이동 발생
# deque.popleft() — O(1)
card = deque([1, 2, 3, 4, 5, 6])
card.popleft()
# 양 끝 포인터만 이동 → 나머지 원소는 이동하지 않음| 자료구조 | 앞에서 꺼내기 | 뒤에 추가 | 임의 접근 |
|---|---|---|---|
list |
O(n) | O(1) 평균 | O(1) |
deque |
O(1) | O(1) | O(n) |
입력 범위가 N ≤ 500,000이다. list로 pop(0)을 쓰면 전체 O(n²)에 가까워져 시간 초과가 발생한다.
| N | list pop(0) 내부 이동 횟수 | deque popleft() 내부 이동 횟수 |
|---|---|---|
| 1,000 | 약 500,000 | 약 1,000 |
| 100,000 | 약 5,000,000,000 | 약 100,000 |
| 500,000 | 약 125,000,000,000 | 약 500,000 |
deque를 쓰는 이유는 단순히 "큐처럼 보여서"가 아니라, 앞에서 꺼내기 연산이 O(1)이기 때문이다.
시간복잡도 정리
| 단계 | 연산 | 복잡도 | 근거 |
|---|---|---|---|
| 초기화 | deque 생성 | O(n) | n개 원소 삽입 |
| 반복 | popleft() × (n-1) | O(n) | 각 호출이 O(1) |
| 반복 | append(popleft()) × (n-1) | O(n) | 각 호출이 O(1) |
| 전체 | — | O(n) | — |
list로 구현했다면 매 반복의 pop(0)이 O(n)이므로 전체 O(n²). N = 500,000에서 시간 초과가 발생한다.
최종 코드
# 큐 — 카드2 (백준 2164)
# https://www.acmicpc.net/problem/2164
from collections import deque
n = int(input())
card = deque(range(1, n+1))
while len(card) > 1:
card.popleft() # 맨 위 카드 버리기
card.append(card.popleft()) # 다음 맨 위 카드를 맨 아래로
print(card[0])버그는 작았지만 파이썬이 에러를 내지 않는 형태로 틀려서 원인을 찾는 데 시간이 걸렸다. 다음에는 메서드를 쓸 때 괄호부터 확인하는 습관을 먼저 챙길 것 같다.
🌿
'크래프톤 정글 > 정글에서 문제풀기' 카테고리의 다른 글
| [정글 알고리즘] - [중] - 백준2493 탑 (0) | 2026.03.16 |
|---|---|
| [정글 알고리즘]-[하]-백준 10828 스택 (0) | 2026.03.16 |
| [정글 알고리즘]-[하]-백준 9933 - 민균이의 비밀번호 (0) | 2026.03.16 |
| [정글 베이직 19] — 해시 테이블 · 성적 관리 (0) | 2026.03.13 |
| [정글 베이직 18] — 연결 리스트 (Linked List) (0) | 2026.03.13 |