BOJ 1158 - 요세푸스 문제 (Python3)

상당히 코딩을 늦게 시작한 편이다. 그래서 자료구조의 자 자도 모르는 상태에서 오늘까지 이르렀다.

오늘이 정확히 16일차고, 그 동안 큐(Queue), 스택(Stack), 덱(Deque) 등의 자료구조를 어떻게 사용하는지 알았다. 

힙(Heap)도 오늘 배웠는데, 아직 체화시키기에는 조금 모자라서 오늘은 덱을 사용하는 요세푸스 문제를 풀겠다.

사실 큐랑 스택을 하나로 묶어서 덱으로 쓰는 게 가장 편하더라. 덱은 큐와 스택을 한 번에 사용 가능하니 말이다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

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

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>

 

---

내 코드

from collections import deque
n,k = map(int, input().split())
x,l = deque(map(str, range(1,n+1))), []
for _ in range(n):
    for i in range(k-1):
        a = x.popleft()
        x.append(a)
    l.append(x.popleft())
print(f"<{', '.join(l)}>")

 

덱은 왼쪽에서도 오른쪽에서도 자료를 밀어넣을 수 있고, 뺄 수 있는 자료 구조이다.

빨대를 더럽게 사용하는 어린아이를 생각하면 편하다. 콜라를 빨대로 빨아들이는 것은 아래쪽에서 콜라(=자료)를 밀어넣고 위쪽으로 콜라가 빠지는 것.

반대로 입에 있는 콜라를 빨대로 뿜는 것은 위쪽에서 콜라가 들어가고 아래쪽에서 콜라가 빠져나오는 것이다.

이번에는 왼쪽에서 자료를 빼기만 할 것이고 오른쪽에선 자료를 집어넣기만 할 것이다. 큐나 다름없다. 덱에서 기능을 제한시킨 큐를 구현하는 것이다.

 

우선 x으로 '1', '2', ..., 'n'이 저장된 덱을 만들자. 그리고 l은 요세푸스 수열이 출력될 리스트다.

순서대로 k번째 사람을 제거한 것이니, 앞에서부터 k-1명을 세어서 그 순서대로 맨 뒤에 보내는 작업을 수행한다. 이것이 이중 for문 중 안쪽에 들어 있는 연산.

그리고 k-1명을 뒤로 넘겼다면? x의 가장 왼쪽에 있는 요소를 떼어서 l로 보내주는 작업을 수행한다.

이렇게 모든 요소가 l로 들어오도록 정확히 n번만 반복해 주면 끝.

 

다음은 ', '로 각 요소를 이어붙인 다음 양 끝에 <>를 붙여서 출력하자.

굳이 x에 1, 2, ..., n이 아니라 문자열로 저장한 이유가 여기에 있다. 안 그러면 에러가 뜨기 때문.

 

이로서 1158번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.