백준 문제 풀이 - 요세푸스 문제 1158번

Joonyeol Sim👨‍🎓·2021년 9월 28일

📜 문제 이해하기

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

💡 문제 재정의

요세푸스 문제는 사람들이 원을 둘러싸고 있을 때 1번부터 K번째 사람을 제거하고, 남은 사람들끼리 다시 K번째 사람을 제거하면서 제거되는 순서를 표현하는 문제이다.

즉, 다음과 같은 그림으로 요약 가능하다. 이 그림에서는 N이 41, k가 2인것으로 보인다.

✏️ 계획 수립

처음에는 문제를 적혀진 그대로 해결하기 위해서 환형 연결 리스트를 구현하기로 마음먹었다.
사람의 수만큼의 노드를 가진 환형 연결 리스트를 만든 다음 1번 노드에서 K번째 노드으로 이동하고 K번째 노드의 값을 출력한 뒤 K-1번째 노드와 K+1번째 노드를 그대로 이으면 마지막 노드까지 진행될 수 있을것이다.

📝 계획 검증

N이 7이고 K가 3일때 다음과 같다. 괄호는 환형이라는것을 보여주기 위해 처음 인자를 뜻한다.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> (1) => 3을 출력
1 -> 2 -> 4 -> 5 -> 6 -> 7 -> (1) => 6을 출력
1 -> 2 -> 4 -> 5 -> 7 -> (1) => 2을 출력
1 -> 4 -> 5 -> 7 -> (1) => 7을 출력
1 -> 4 -> 5 -> (1) => 5을 출력
1 -> 4 -> (1) => 1을 출력
4 => 4를 출력

💻 계획 수행

class Node:
    def __init__(self, number):
        self.number = number
        self.next = None


class CircularLinkedList:
    def __init__(self):
        self.head = Node('head')
        self.head.next = self.head
        self.cur_node = self.head

    def insert(self, item, new):
        new_node = Node(new)
        cur_node = self.find(item)
        new_node.next = cur_node.next
        cur_node.next = new_node

    def find(self, item):
        cur_node = self.head
        while cur_node.number != item:
            cur_node = cur_node.next
        return cur_node

    def find_previous(self, item):
        cur_node = self.head
        while cur_node.next.number != item:
            cur_node = cur_node.next
        return cur_node

    def print(self):
        cur_node = self.head
        while cur_node.next.number != 'head':
            print(cur_node.number, end=' -> ')
            cur_node = cur_node.next
        print(cur_node.number)

    def remove(self, gap):
        cnt = 0
        while cnt < gap:
            self.cur_node = self.cur_node.next
            if self.cur_node.number != 'head':
                cnt += 1
        prev_node = self.find_previous(self.cur_node.number)
        prev_node.next = prev_node.next.next
        return str(self.cur_node.number)


if __name__ == '__main__':
    N, K = map(int, input().split())

    people_list = CircularLinkedList()
    people_list.insert('head', 1)
    for i in range(2, N + 1):
        people_list.insert(i - 1, i)

    print("<", end='')
    for i in range(N - 1):
        print(people_list.remove(K), end=', ')
    print(people_list.remove(K), end='')
    print(">")

🤔 회고

위 해결 방법은 성공적으로 작동했지만 다시 생각해보니 환형 큐로도 더 간단하게 생각할 수 있을 것 같아 알고리즘을 환형 큐로 개선해보았다.

✏️ 계획 수립 2

환형 큐를 통해 K번째 순서가 올때까지 가장 앞의 순서부터 dequeue를 한다.
dequeue한 값들은 다시 큐의 뒤에 enqueue를 한다.
K번째 순서가 오면 값을 프린트하고 삭제한다.
위 과정을 N번 반복한다.

📝 계획 검증 2

N이 7이고 K가 3일때 다음과 같다.
[1, 2, 3, 4, 5, 6, 7] -> [3, 4, 5, 6, 7, 1, 2] => 3 삭제
[4, 5, 6, 7, 1, 2] -> [6, 7, 1, 2, 4, 5] => 6 삭제
[7, 1, 2, 4, 5] -> [2, 4, 5, 7, 1] => 2 삭제
[4, 5, 7, 1] -> [7, 1, 4, 5] => 7 삭제
[1, 4, 5] -> [5, 1, 4] => 5 삭제
[1, 4] -> [1, 4] => 1 삭제
[4] => 4 삭제

💻 계획 수행 2

from collections import deque

if __name__ == '__main__':
    N, K = map(int, input().split())

    people_queue = deque([i+1 for i in range(N)])
    index = 0
    print('<', end='')
    for i in range(N - 1):
        for _ in range(K - 1):
            people_queue.append(people_queue.popleft())
        print(f'{people_queue.popleft()}, ', end='')
    print(f'{people_queue.popleft()}>', end='')