백준_1158 - 요세푸스 문제

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

문제 분석

• 1번부터 N번까지 사람들이 원형으로 앉아 있음.
• K번째 사람을 순서대로 제거하며, 모든 사람이 제거될 때까지 반복.
• 제거된 순서를 출력하는 문제.

예시: N = 7, K = 3일 때 → 제거 순서: 3, 6, 2, 7, 5, 1, 4

 

해결 방법

1. 원형 연결 리스트(Circular Linked List) 방식

• 직접 원형 구조를 구현하여 K번째 사람을 찾아 제거.
• 노드 구조와 연결 관계를 구현해 매번 이동 및 제거 처리.

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

class CircularLinkedList:
    def __init__(self, N):
        self.head = None
        self.tail = None
        self.create_list(N)

    def create_list(self, N):
        prev_node = None
        for i in range(1, N+1):
            new_node = Node(i)
            if not self.head:
                self.head = new_node
            else:
                prev_node.next = new_node
            prev_node = new_node
        prev_node.next = self.head
        self.tail = prev_node

    def remove_kth(self, K):
        result = []
        current = self.head
        prev = self.tail

        while current.next != current:
            for _ in range(K-1):
                prev = current
                current = current.next
            result.append(current.value)
            prev.next = current.next
            current = current.next

        result.append(current.value)
        return result

def josephus(N, K):
    cll = CircularLinkedList(N)
    return cll.remove_kth(K)

N, K = map(int, input().split())
print("<"+", ".join(map(str, josephus(N, K)))+">")

2. deque 회전 방식

• collections.deque의 rotate()를 이용해 K번째 사람을 맨 앞으로 회전.
• popleft()로 제거.

from collections import deque

def josephus(N, K):
    queue = deque(range(1, N+1))
    result = []

    while queue:
        queue.rotate(-(K-1))
        result.append(queue.popleft())

    return result

N, K = map(int, input().split())
print("<"+ ", ".join(map(str, josephus(N, K))) +">")

 

시간 복잡도

방식이동 및 제거 비용반복 횟수총 시간 복잡도

Linked List	K번 이동 O(K) + 삭제 O(1)	N번	O(NK)
deque 회전	회전 O(K) + 삭제 O(1)	N번	O(NK)