백준 1158번: 요세푸스 문제 (Python)

1158번: 요세푸스 문제

처음엔 linked list로 순환 구조를 만들어서 풀려다가 아직 class를 잘 못다루다 보니 선언부분에서 막혔다.

class node:
    def __init__(self, data) -> None:
        self.data = data
        self.next = None
    
    def nextNode(self):
        return self.next
    
    def setNext(self, next):
        self.next = next

head = Node(1)
head.next = Node(2)
heads = head.next
for i in range(3, N+1):
    heads = heads.next
    heads = Node(i)
heads.next(Node(1))

class에 nextnode를 만들어 다음 node를 가르키게 하려 했는데 한번 호출한 head가 휘발되어 다음 Node를 가르키게 되지 않아 구현하지 못했다.

그다음엔 dictionary를 사용해 index를 직접 더해가면서 false인 부분은 건너뛰고 true인 부분만 체크하여 출력하는 방식으로 구현 해보려 했다.

N, K = map(int, input().split())
ndict = {}
for i in range(1, N+1):
    ndict[i] = True
count = 1
nlist = []
print(ndict)

for i in range(N):
    for j in range(K):
        check = 0
        while True:
            count += 1
            if count > N:
                count = 1
                if ndict[N]:
                    check += 1
            if ndict[count]:
                check += 1
            if check == K:
                break
    ndict[count] = False
    nlist.append(count)
    print(ndict)
print(nlist)

이 또한 복잡한 구조에 패턴이 중간에 꼬여 더 쓰다간 코드가 더 복잡해질 것 같아 다른 방식을 생각했다.

마지막으로 list를 활용해서 앞에서 빼내고 뒤로 넣으면서 직접 카운팅하는 방식이다. pop(0)는 시간복잡도가 O(n)이기 때문에 deque의 popleft()를 사용해 O(1)로 줄였다.

from collections import deque

N, K = map(int, input().split())

nlist = [i for i in range(1, N+1)]
nlist = deque(nlist)
plist = []
for _ in range(N):
    for i in range(K):
        nlist.append(nlist.popleft())
    plist.append(nlist.pop())
print('<' , end='')
print(*plist , sep=', ', end='')
print('>' , end='')

출력은 unpacking하여 리스트를 부분적으로 나눠 구현해줬다.

 

공부한 내용:

03. 파이썬으로 연결 리스트 구현하기

관련된 문제:

5397번: 키로거 (Python)