[백준 1158] 요세푸스 문제 - Python(큐, 링크드 리스트)

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

 

 

1차 풀이

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    numbers = deque(range(1, N+1, 1))
    deleted_numbers = []

    i = -1
    count = 0
    while len(deleted_numbers) != N:
        i += 1

        if i >= N:
            i = 0

        if numbers[i] not in deleted_numbers:
            count += 1
            if count == K:
                count = 0
                deleted_numbers.append(numbers[i])
                continue
    return "<" + ", ".join(map(str, deleted_numbers)) + ">"

print(get_answer())

 

문제점

 

- 효율성 문제

• 삭제 여부 확인 방식:
  코드에서는 원래의 numbers 데크에서 값을 제거하지 않고, 별도의 deleted_numbers 리스트에 추가한 후, 매번 if numbers[i] not in deleted_numbers:로 삭제 여부를 확인한다. 이 방식은 리스트의 멤버십 검사가 O(n) 시간 복잡도를 가지므로, N이 5000과 같이 큰 경우 불필요하게 많은 연산을 수행하게 되어 성능 문제가 발생할 수 있다.
• 불필요한 자료구조 사용:
  데크(deque)를 선언해두었지만, 데크의 효율적인 회전(rotate) 기능이나 popleft() 등을 활용하지 않고 단순히 인덱스 접근 방식으로 사용하고 있습니다

---

개선된 코드

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    dq = deque(range(1, N+1, 1))
    result = []

    while dq:
        for _ in range(K - 1):
            dq.append(dq.popleft())
        result.append(dq.popleft())


    return "<" + ", ".join(map(str, result)) + ">"

print(get_answer())

 

개선 효과

- 매번 불필요한 인덱스 접근이나 멤버십 검사를 하지 않아 시간 복잡도를 O(N)으로 줄일 수 있다.

---

Python rotate 메서드 활용 코드

from collections import deque
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
dq = deque(range(1, N + 1))
result = []

while dq:
    dq.rotate(-(K - 1))  # K-1번 왼쪽으로 회전
    result.append(dq.popleft())

print("<" + ", ".join(map(str, result)) + ">")

 

---

요세푸스 문제는 원형 구조를 활용해 특정 규칙에 따라 요소들을 제거하는 시뮬레이션 문제인데, 그 개념 자체는 원형 연결 리스트 (circular linked list)와 매우 유사하다.

 

주요 포인트

• 원형 연결 리스트:
  노드들이 원형으로 연결되어 있어 마지막 노드의 다음이 첫 번째 노드가 된다. 요세푸스 문제에서는 이 구조를 통해 K번째 원소를 계속해서 찾아 제거하는 과정을 구현한다.
• 시뮬레이션:
  문제의 해결 방법은 실제로 원형 연결 리스트를 사용해 구현할 수도 있고, Python의 deque 같은 자료구조를 이용해 원형 큐의 동작(회전 및 제거)을 시뮬레이션하는 방식으로도 구현할 수 있다.
  예를 들어, deque를 사용하면 rotate()나 popleft() 같은 메서드로 간단하게 원형 구조를 흉내낼 수 있다.
• 알고리즘 선택:
  요세푸스 문제는 원형 연결 리스트를 이용하는 시뮬레이션 문제로 접근할 수 있지만, 경우에 따라 수학적인 공식을 활용해 더 효율적으로 풀 수도 있다. 단, 일반적으로 K가 임의의 값일 때는 시뮬레이션 방법이 가장 직관적이다.