[백준 1158번] 요세푸스 문제

원본 링크

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

문제

요세푸스 문제는 다음과 같다.

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

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

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

출력

예제 입력

7 3

예제 출력

<3, 6, 2, 7, 5, 1, 4>

주 알고리즘 분류

• 자료구조
• 큐

나만의 풀이

파이썬에서는 리스트를 활용해서 큐를 구현할 수 있다.
리스트에서 제공되는 기본 메소드인 .pop()과 .append()를 활용하면 된다.
아래에 간단한 구현 예시 코드가 있다.

Q = [1, 2, 3, 4]
Q.pop(0)  # 1이라는 원소가 뽑힌다.
Q.append(5)  # 원소 4 오른쪽에 5가 추가된다.
print(Q)

.pop(0)라는 메소드는 주어진 리스트의 0번째 원소를 뽑는 기능을 수행한다.
해당 예시에서 0번째 원소는 1이므로, 1이 뽑히게 된다.
.append()는 밥 먹듯이 쓰는 메소드이므로 굳이 적어놓지는 않겠다.

최종적으로 Q를 출력하게 되면 [2, 3, 4, 5]라는 결과가 뜰 것이다.

또한 여기에서 언급하진 않았지만 파이썬 자체에서도 queue라는 구조체를 제공하고 있다.
그러나 실제로 위 방식을 써서 동작을 구현하게 되면 간혹 제한시간 내에 통과하지 못하는 불상사가 발생한다!
따라서, 우리는 데크(deque) 라는 친구를 활용해서 큐를 만들려고 한다.

데크는 원래 양방향으로 원소를 넣고 빼고 할 수 있는 큐라 보면 된다.
애당초 그 이름도 Double-ended queue의 약자이다!
따라서 총 4가지의 삽입 및 추출 메소드를 지원하게 된다.
.append(), .appendleft(), .pop(), .popleft()가 그 친구들이다.
해당 메소드들의 차이는, 뒤에 left 붙은건 맨 앞의 원소를, 없으면 맨 뒤의 원소를 기준으로 동작이 수행되는 것 뿐이다.

그래서 왜 데크를 쓰는가 찾아보면, 다음의 차이가 있다.
파이썬의 리스트의 시간 복잡도는 O(n)이나, Deque의 시간 복잡도는 무려 O(1)이나 된다. (!)
성능 차이가 엄청 뚜렷한데 굳이 다른 자료구조를 쓸 필요가 있을까.
따라서 큐건 스택이건 파이썬의 데크를 import해서 사용하면 좋은 효율을 보일 수 있다.

최종 코드는 다음과 같다.
맨 마지막의 주어진 양식대로 출력하는 부분은 크게 설명하지 않고 생략하려 한다.
(귀찮아서 간단하게 적으면, 마지막 순서에서만 ', '를 출력 안 하도록 코드를 짰다.)

# 속도를 위해 deque 사용.
from collections import deque

# 초깃값
n, k = map(int, input().split())

# 데크 선언
D = deque([i+1 for i in range(n)])

picked = []  # 뽑아낸 사람을 담을 배열
while len(D) > 1:
    for _ in range(k-1): D.append(D.popleft())
    picked.append(D.popleft())
picked.append(D.popleft())  # 남은 원소 하나 append

# 주어진 양식대로 출력.
print('<', end='')
for i, p in enumerate(picked):
    print(p, end='')
    if i+1 != n: print(', ', end='')
print('>')

여기선 .append와 .popleft 만을 활용해서 순환을 하는 방식을 썼다.
그러나 데크에서 제공하는 메소드중에서 .rotate(값)라는 친구도 있다.
양수를 넣으면 시계방향(오른쪽)으로, 음수를 넣으면 반시계방향(왼쪽)으로 원소를 회전시키는 역할이다.
만일 위 메소드를 이용하면 다음의 형태로 코드를 짤 수도 있겠다.

picked = []
while len(D) > 1:
    D.rotate(-k)  # 바뀐 부분!
    picked.append(D.pop())  # 바뀐 부분!
picked.append(D.popleft())

for문을 k-1번 돌면서 popleft와 append 연산을 반복 수행하는 구문에 rotate를 넣었다.
다만 여기선 왼쪽으로 원소를 회전해야 원하는 결과를 얻을 수 있다.

자료구조 중에서도 초반에 배우는 큐의 원리와 이를 활용하는 방법만 알고 있으면 적어도 파이썬에서는 쉽게 풀 수 있는 문제라고 본다.
다만 맨 마지막의 출력 양식을 맞추는 게 가장 까다로웠다 생각이 든다.