5. 공주구하기(큐)_파이썬

전체코드

import sys
from collections import deque
# 입력값: 8 3
sys.stdin=open("C:\\input.txt",'rt')
n, k = map(int,input().split())
print(n,k)

dq= list(range(1,n+1))
dq = deque(dq)
print(dq)

while dq:
    for _ in range(k-1):
        cur = dq.popleft()
        dq.append(cur)
    dq.popleft()

    if len(dq) == 1:
        print(dq[0])
        dq.popleft()

 

---

 

이 코드는 요세푸스 문제(Josephus Problem)를 해결하는 알고리즘
큐(Deque)를 활용해서 원형으로 사람을 제거하면서 마지막 남은 사람을 찾는 방식🚀

---

📌 요세푸스 문제란?

• 1번부터 n번까지 원형으로 앉아 있는 사람들이 있어.
• k번째 사람을 계속 제거하면서 마지막 남은 사람을 찾는 문제!

📝 예제: n = 8, k = 3

 

초기 상태: [1, 2, 3, 4, 5, 6, 7, 8] 
(3번째 제거) → 3 제거 → [1, 2, 4, 5, 6, 7, 8] 
(3번째 제거) → 6 제거 → [1, 2, 4, 5, 7, 8] 
(3번째 제거) → 9 제거 → [1, 2, 4, 5, 7] ... 마지막 남은 사람: ?

이 과정을 코드로 구현하는 거야!

---

🔍 코드 분석

1️⃣ 입력 처리

 

import sys from collections 
import deque sys.stdin = open("C:\\input.txt", 'rt') 
n, k = map(int, input().split()) print(n, k)

• n, k를 입력받음
• 예제 입력: 8 3 → n = 8, k = 3
• print(n, k) → 입력값 확인용 (실제 로직에는 필요 없음)

---

2️⃣ 큐(Deque) 초기화

 

dq = list(range(1, n + 1)) 
dq = deque(dq) 
print(dq)

• range(1, n+1) → [1, 2, 3, ..., n] 리스트 생성
• deque(dq) → 큐(Deque)로 변환
  (리스트로 해도 되지만, deque를 쓰면 popleft()가 O(1)로 더 빠름!) 

💡 deque란?

• 양쪽 끝에서 빠르게 삽입/삭제 가능
• popleft() → O(1), append() → O(1)
  (일반 리스트는 pop(0)이 O(n)으로 느림)

---

3️⃣ 요세푸스 순열 계산

python

복사편집

while len(dq) > 1: 
for _ in range(k-1): # k-1번 앞에서 빼서 뒤로 이동 
cur = dq.popleft() 
dq.append(cur) 
dq.popleft() # k번째 사람 제거

• (k-1)번 앞에서 빼서 뒤로 보냄
  → popleft() 후 append()
• k번째 사람을 제거
  → popleft() (그냥 버림)

---

4️⃣ 마지막 남은 사람 출력

 

print(dq[0])

• 큐에 남은 마지막 사람을 출력!

---

💡 실행 예제

입력

8 3

큐 상태 변화

단계큐 상태 (dq)제거된 사람

초기	[1, 2, 3, 4, 5, 6, 7, 8]	-
1	[4, 5, 6, 7, 8, 1, 2]	3
2	[7, 8, 1, 2, 4, 5]	6
3	[2, 4, 5, 7, 8]	1
4	[7, 8, 2, 4]	5
5	[4, 7, 8]	2
6	[4, 7]	8
7	[7]	4

출력 결과

 

7

➡ 마지막 남은 사람: 7

---

⏳ 시간 복잡도 분석

연산복잡도

popleft()	O(1)
append()	O(1)
while len(dq) > 1	O(n) (반복문)
내부 for 루프	O(k) (매번 k-1번 이동)

• 총 시간 복잡도: O(n * k)
• k가 작을수록 빠름, k ≈ n이면 최악의 경우 O(n²)
• n이 클 경우 k-1번 이동 대신 rotate(-k)를 사용하면 O(n) 가능!

---

✅ 정리

✅ 요세푸스 문제 해결 (큐 사용)
✅ Deque 활용 → O(n * k) → rotate()로 O(n) 최적화 가능
✅ popleft() & append()를 활용해 원형 큐 구현