[1158] 요세푸스 문제

백준 Silver IV | 1158 | Python | 문제 링크

문제 설명

1번부터 N번까지 N명의 사람이 원을 이루어 앉아있고, 양의 정수 K (≤ N)가 주어진다. 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. N과 K가 주어지면 요세푸스 순열을 구하라.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

입출력 예

입력	출력
7 3	<3, 6, 2, 7, 5, 1, 4>

 

나의 풀이

풀이 1 - 아이디어 확인과 버그 수정

요세푸스 문제를 처음 읽었을 때 머릿속에 바로 deque가 떠올랐다. N명이 원형으로 앉아서 k번째 사람을 순서대로 제거하는 문제인데, 원형 구조를 deque로 흉내 내면 딱이었다.

앞에서 k-1명을 꺼내 뒤로 붙이면, 지금 앞에 나와 있는 사람이 k번째가 됩니다. 그 사람을 꺼내 결과에 추가하면 됩니다.

for _ in range(k - 1):
    q.append(q.popleft())
result.append(q.popleft())

두 줄이다. 자료구조가 문제의 구조와 정확히 맞아떨어지는 순간이라서 기분이 좋았다. 이 정도면 금방 끝나겠다 싶었다.

from collections import deque
import sys
input = sys.stdin.readline
q = deque()
result = []
n, k = map(int, input().split())
for i in range(1, n+1):
    q.append(i)
while q:
    for _ in range(k-1):
        q.append(q.popleft())
    result.append(q.popleft)
print("<", ", ".join(map(str, result)) ,">", end="")

틀렸다는 피드백이 돌아왔을 때 그 자신감이 와장창 무너졌습니다.

버그 1 — 괄호 하나

result.append(q.popleft)

q.popleft에 괄호가 없습니다.

이 코드는 popleft를 호출한 게 아니라 함수 객체 자체를 result에 집어넣은 것입니다. 실행이 멈추지도 않고 오류도 나지 않습니다. while q 루프가 끝난 후 result를 출력하면 함수 객체들이 줄줄이 나옵니다. 파이썬에서는 함수 자체도 값이기 때문에 append에 넣는 것 자체는 문제가 없습니다.

그게 더 당혹스러웠습니다. 에러가 났다면 바로 눈에 띄었을 텐데, 코드는 아무 일 없다는 듯 돌아갔습니다. 출력이 이상하게 나와서야 뭔가 잘못됐다는 것을 알았습니다.

q.popleft와 q.popleft()는 문자 하나 차이지만 하나는 값이고 하나는 함수 참조입니다. 눈으로 보면서도 지나친 종류의 버그였습니다.

버그 2 — print의 기본 동작

print("<", ", ".join(map(str, result)) ,">", end="")

기대했던 출력은 <1, 2, 3, ...>입니다. 실제 출력은 < 1, 2, 3, ... >였습니다. 꺾쇠 옆에 공백이 생겼습니다.

print는 여러 인자를 받을 때 sep=" "을 기본값으로 씁니다. "<"와 ", ".join(...) 사이에 공백이 들어가고, 마지막 ">"와도 공백이 생깁니다.

알고 보면 당연한 동작인데 당시에는 예상 밖이었습니다. end=""로 줄바꿈은 신경 썼으면서 sep은 생각하지 못했습니다.

풀이 2 - 최종 제출 코드

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

q = deque()
result = []
n, k = map(int, input().split())

for i in range(1, n+1):
    q.append(i)

while q:
    for _ in range(k-1):
        q.append(q.popleft())
    result.append(q.popleft())

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

두 곳을 고쳤다. 통과했다.

풀이 3 - rotate() 활용

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

n, k = map(int, input().split())
q = deque(range(1, n+1))
result = []

while q:
    q.rotate(-(k-1))
    result.append(q.popleft())

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

deque.rotate(-n)은 앞에서 n개를 꺼내 뒤로 붙이는 동작을 내부적으로 수행합니다. 직접 for _ in range(k-1): q.append(q.popleft())라고 쓰는 것과 결과는 동일합니다.

for 루프 두 줄이 q.rotate(-(k-1)) 한 줄로 줄었습니다. 성능 차이는 없습니다. 둘 다 O(nk)입니다.

rotate()를 알고 있으면 가독성이 더 올라갑니다. 단, "앞에서 n개를 뒤로 보낸다"는 직관이 먼저 있어야 메서드 이름을 봤을 때 동작이 머릿속에 그려집니다.