11866: 요세푸스 문제 0 - Python

문제

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

풀이 1 (오답)

N, K = map(int, input().split())
arr = list(range(1, N+1))
ans = []
i = K-1

while True:
    ans.append(arr[i])
    del arr[i]
    i = (i+K-1) % len(arr)

    if len(arr) == 1:
        ans.append(arr[0])
        break

print("<" + ", ".join(map(str, ans)) + ">")

• ZeroDivisionError가 발생했다.
• 반례: N = 1인 모든 경우
  -> N = 1, K = 1일 때, ZeroDivisionError 발생
  -> N = 1, K > 1일 때, IndexError 발생

풀이 2 (수학)

N, K = map(int, input().split())
arr = list(range(1, N+1))
ans = []
i = K-1

if N == 1:
    ans = [1]
else:
    while True:
        ans.append(arr[i])
        del arr[i]
        i = (i+K-1) % len(arr)

        if len(arr) == 1:
            ans.append(arr[0])
            break
            
print("<" + ", ".join(map(str, ans)) + ">")

• 풀이 1에서 N = 1인 경우를 예외처리했다.
• 맞긴 하지만 추하게 푼 것 같다.

풀이 3 (deque, 개랄발랄님 풀이)

from collections import deque

N, K = map(int, input().split())
queue = deque(range(1, N+1))
ysps = []

while queue:
    for _ in range(K-1):
        queue.append(queue.popleft())
    ysps.append(queue.popleft())

print("<" + ", ".join(map(str, ysps)) + ">")

• deque을 사용했다. 천재적!
• 문제를 처음 봤을 때 원형 큐를 구현하고자 deque을 사용하려 했다가 너무 복잡해져서 그만뒀는데, 이렇게도 할 수 있구나.

---

오늘의 교훈

• deque은 신이다.
• 큐를 구현할 때는 deque을 쓰자.

참고 자료

• [백준/Python][Silver V] 요세푸스 문제 0 - 11866