알고리즘 문제풀이: 요세푸스

비트코인에 맛들려서 1주일의 시간을 태웠다.

Circular list

요세푸스 문제

백준 1158번

#node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

#circular list
class CircleList:
    def __init__(self):
        self.head = None
        self.size = 0

    def insert(self, prev_node, data):
        node = Node(data)
        self.size += 1

        if prev_node:
            node.next = prev_node.next
            prev_node.next = node
        else:
            self.head = node
            node.next = node

    def traverse(self):
        current = self.head

        while True:
            yield current.data
            if current.next is self.head:
                break
            else:
                current = current.next

    def delete(self, prev_node):
        self.size -= 1

        if prev_node.next is self.head:             # delete head; class.size >1
            if self.size != 0:
                prev_node.next = self.head.next
                self.head = prev_node
            else:                                   # delete head; class.size = 1
                self.head = None
        else:
            prev_node.next = prev_node.next.next


def reaching_node(circle_list, num):
    current = circle_list.head
    for _ in range(1, num):
        current = current.next
    return current


cc_list = CircleList()
n, m = map(int, input().split())

# create circle_list
for i in range(n, 0, -1):
    cc_list.insert(cc_list.head, i)
print("<", end='')

# 요세푸스 순열; except for last node
for _ in range(1, n):
    crt = reaching_node(cc_list, m)
    print(crt.next.data, end=', ')
    cc_list.head = crt
    cc_list.delete(crt)
print(cc_list.head.data, end='>')

circular list의 경우 size가 커질수록 노드에 접근하는 것이 쉽지 않았다. 클래스 내부 매서드로 구현하는 것도 좋겠지만
배운 클래스는 구현하지 않았음으로 문제를 풀기 위해서 임시로 사용했다.
insert와 delete의 매개변수 중에 prev_node가 접근하기 까다롭고 알고리즘을 이해하기 힘들었다.
circular list의 내부 매서드도 조건에 의해 나누는 것이 마냥 쉽지는 않았다.