[백준 11866번] 요세푸스 문제 0 - python

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

📌 문제 탐색하기

목표

• 원에서 사람들이 제거되는 순서인 요세푸스 순열을 출력한다.

입력값

• 첫째 줄에 사람 수인 n과 번째를 나타내는 k가 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
• ex)
• 7 3

출력값

• (n, k)-요세푸스 순열을 출력한다.
• ex)
• <3, 6, 2, 7, 5, 1, 4>

📌 코드 설계하기

해결 아이디어

• n+1 길이의 False로 채워진 Boolean 배열을 만들고 True의 개수가 K개일 때 출력하면 되나?
• 흠 그러면 while문과 그 안에 for문이 들어가야되고 cnt도 k가 될때까지 판단해야 해서 계산량이 많다.
• 그러면 어짜피 삽입할 때 O(N)은 소비되고 그 뒤로 삭제가 빠른 linked list를 써서 해결해보자.
• k-1만큼 이동해서 next_node를 삭제하고 next_node→ next_node와 연결시켜주면 된다.

📌 1차 제출 코드

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

class LinkedList:
    def __init__(self, num, next_node = None):
        self.num = num
        self.next_node = next_node
    
head = LinkedList(0)
current_node = head
for i in range (1, n+1):
    newNode = LinkedList(i)
    current_node.next_node = newNode
    current_node = current_node.next_node
    if i == n:
        current_node.next_node = head.next_node
current_node = head
print("<", end="")

while(True):
    for i in range(k-1):
        current_node = current_node.next_node
    if current_node.next_node == current_node:
        print(current_node.next_node.num, end=">\\n")
        break
    else:
        print(current_node.next_node.num, end=", ")
        current_node.next_node = current_node.next_node.next_node

• 출력 초과가 떴다!
• ?? 1, 1을 입력해보니 1이 무한으로 출력됐다. 생각해보니 for문이 k-1까지 돌아서 k=1일 때는 해당 for문이 실행되지 않고 else로 들어가버린다. 그러면 print만 무한으로 하는 것이다!!
• k=1를 따로 빼서 linked list를 모두 출력하고 끝내도록 했다!

📌 정답 코드

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

class LinkedList:
    def __init__(self, num, next_node = None):
        self.num = num
        self.next_node = next_node
    
head = LinkedList(0)
current_node = head
for i in range (1, n+1):
    newNode = LinkedList(i)
    current_node.next_node = newNode
    current_node = current_node.next_node
    if i == n:
        current_node.next_node = head.next_node
current_node = head
print("<", end="")
if k == 1:
    for i in range(n): 
        current_node = current_node.next_node
        if i == n-1:
            print(current_node.num, end=">\\n")
            exit()
        print(current_node.num, end=", ")
while(True):
    for i in range(k-1):
        current_node = current_node.next_node
    if current_node.next_node == current_node:
        print(current_node.next_node.num, end=">\\n")
        break
    else:
        print(current_node.next_node.num, end=", ")
        current_node.next_node = current_node.next_node.next_node

시간 복잡도

• 입력할 때 리스트를 초기화 하므로 O(N)
• while문내의 코드는 k-1번 실행되니까 O(K-1)
• 그리고 while문은 n번 실행될테니 O(NK)
• 최종적으로 $O(N^2)$