bj1158 요세푸스 문제

요세푸스 문제
Circularlist를 이용해야한다.
이 문제를 풀기 위해 자료구조에 대해 배웠고
결국 풀어냈다!!

음.. 우선 각 node의 object를 생성하는 class와
Circular_Linked_list 의 object를 생성했다.

traverse()는 data가 잘 들어갔는지 확인하려고 생성했고
insert와 delete만 실질적으로 이용하게 된다!

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


class CircularList:
    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 == self.head:
                break
            else:
                current = current.next

    def delete(self, prev_node):
        self.size -= 1
        if prev_node.next != self.head:
            prev_node.next = prev_node.next.next
        else:
            if prev_node != self.head:
                self.head = self.head.next
                prev_node.next = self.head
            else:
                self.head = None


#n, k = map(int, input().split())
n, k = 7, 3


point = CircularList()
point.insert(None, 1)
_current = point.head
for i in range(2, n + 1):
    point.insert(_current, i)
    _current = _current.next

print('<', end='')
#현재위치를 head전을 가리키도록 할 거임!
_current = point.head
for _ in range(n - 1):
    _current = _current.next

while point.size != 1:
    for _ in range(k - 1):
        _current = _current.next
    print(_current.next.data, end=', ')
    point.delete(_current)
print(point.head.data, end='>')

핵심 code는 아랫부분이다.

1. 나는 구현에서 prev_node를 가리켜서 insert와 delete를 하기 때문에 delete를 하기 위해서 head node의 전 node를 가리키도록 할 필요가 있었다.

2. 전 node로 정렬 후 k변수를 이용해서 current 위치를 조정해주었다. data를 출력 후 delete를 진행해주었다.

3. 이 때 garbage collection이 일어나지 않나 걱정했는데 생각해보니 current가 이미 가리키고 있기 때문에 garbage collection이 일어나지 않고 잘 돌아갔다!

근데 이 문제 바보같이 map함수 오타 때문에 runtime error 2번 뜨고 수정해서 3트만에 성공함.. 그래서 정답률 뚝 떨어짐 ㅠㅠ 아 txt file로 확인하고 제출해야겠다...

++list로도 구현을 해보았다.
상당히 위에 code보다 간단하지만 running time을 본다면
list로 구현하는 것보다 circular linked list로 구현하는 것이 훨씬 빠르다!

n, k = map(int, input().split())

card = []
for i in range(1, n+1):
    card.append(i)

index = 0
print('<', end='')
while len(card) != 1:
    for _ in range(k-1):
        index += 1
        if index == len(card):
            index = 0
    print(card[index], end=', ')
    card.pop(index)
    if index == len(card):
        index = 0
print(card[0], end='>')