[Python] BOJ 1158 - 요세푸스 문제(Circular Linked List)

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

1158번: 요세푸스 문제

이중연결리스트 문제를 풀고 삘받아 원형연결리스트문제까지 도전해보았다.

이것도 역시 단순 수식으로 짧게 푸는 방법도 있지만, 원형 연결리스트로 풀어보았다.

import sys
input = sys.stdin.readline
class CList:
    class Node:
        def __init__(self,item,link):
            self.item = item
            self.next = link
    
    def __init__(self):
        self.last = None
        self.size = 0
    
    def insert(self,item):
        n = self.Node(item,None)
        if(self.size == 0):
            n.next = n
            self.last = n
        else:
            n.next = self.last.next
            self.last.next = n
        self.size += 1
    
    def delete(self,p):
        x = p.next
        if(self.size == 1):
            self.last = None
        else:
            p.next = x.next
        self.size -= 1
        return x.item

    def print_list(self,N,K):
        L = []
        p = self.last
        for _ in range(N):
            for j in range(K-1):
                p = p.next
            L.append(self.delete(p))
        return L

N,K = map(int,input().split())
c = CList()
for i in range(N,0,-1):
    c.insert(i)
L = c.print_list(N,K)
print('<',end='')
print(', '.join(str(x) for x in L),end='')
print('>')

특이하게 문제푸는 시간보다 마지막에 출력 부분을 구현하는게 더 오래걸렸다..

출력 형식이 <3, 6, 2, 7, 5, 1, 4> 이런식으로 되어있어서 join함수를 검색해 쓰느라 고생했다.