[Baekjoon] 1158/요세푸스 문제/Python/파이썬/자료구조/연결리스트

井·2024년 12월 17일

문제풀이

목록 보기

7/56

💡문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제입력

7 3

예제출력

<3, 6, 2, 7, 5, 1, 4>

📖내가 작성한 Code

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


class Stack:
    def __init__(self):
        self.top_node = None
        self.first_node = None

    def push(self, data: int):
        first_node = Node(1)
        self.top_node = first_node
        self.first_node = first_node
        for num in range(2, data + 1):
            new_node = Node(num)
            self.top_node.next = new_node
            self.top_node = new_node
        self.top_node.next = self.first_node

    def pop(self, data: int):
        result = []

        while self.top_node != self.top_node.next:
            for _ in range(data - 1):
                self.top_node = self.top_node.next
            pop_node = self.top_node.next
            self.top_node.next = pop_node.next
            result.append(pop_node.data)

        result.append(self.top_node.data)

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


def main():
    new_stack = Stack()
    n, k = map(int, input().split())
    new_stack.push(n)
    print(new_stack.pop(k))


if __name__ == "__main__":
    main()

✍️풀이과정

보통 큐 두가지를 사용하거나, 수학적으로 접근하는 방법이 있는데, 연결리스트를 활용해서 마지막 노드를 처음 노드와 연결시켜주면서 원형으로 만들었다. 수학적으로 하는 것이 시간적으로는 이득인듯. 아래에는 내가 1년전에 풀었던 코드이다.

import sys
input = sys.stdin.readline

N,K = map(int,input().split())
idx= 0
lst = list(i for i in range(1,N+1))
yosepusu = []
while len(lst)>1:
    idx = (idx+K-1)%len(lst)
    yosepusu.append(lst.pop(idx))
yosepusu.append(lst[0])
print('<',end = '')
for i in yosepusu[:-1]:
    print(i,end=', ')
print(yosepusu[-1],end='')
print('>',end = '')

이 코드가 더 시간적으로 빠르다. 왜냐면 pop할 때, 내가 만든 연결리스트는 전부 순회하지만, 위의 코드는 수학적으로 index를 바로 찾아가기 때문이다. 지금 피드백 하자면,
1. lst = list(range(1, N+1)) 이런 식으로 단순화 가능(제너레이터를 이해하지 못한듯)

파이썬에서 제너레이터(generator)객체란?

반복 가능한 객체를 쉽게 만들 수 있게 해주는 특별한 함수나 표현식

함수를 호출할 때 한 번에 모든 결과를 한꺼번에 만드는 것이 아니라, 필요할 때마다 결과를 하나씩 생성하는 방식으로 동작

(1) 게으른 계산(Lazy Evaluation): 결과를 한 번에 모두 계산하지 않고, 다음 값이 필요할 때(next()) 그 값을 계산 -> 메모리 효율 좋음
(2) 반복 가능한 객체임
(3) 한 번 순회하면 사라지는 일회성
(4) 필요한 순간에 값을 하나씩 생성(yield(함수의 실행 상태가 정지되는 키워드) 사용)

print 구문이 많다 정도 인듯

🧠 코드 리뷰

Python의 deque 이용 : 학습 목적으로 직접 구현하는 것은 좋지만, 실제 프로젝트에서는 collections.deque와 같은 내장 자료구조를 사용하는 것이 더 효율적이고 안정적
직접적 수학적 해법 고려 : 현재 방식은 매번 k-1번 이동하여 O(n*k)의 시간 복잡도를 가지기에 방식 변경
클래스와 매서드명 개선: first_node는 원형 리스트의 시작점을 의미하므로 head로 변경

🛠️AI 개선 코드

class Node:
    """단일 연결 리스트의 노드 클래스"""
    def __init__(self, data):
        self.data = data
        self.next = None


class JosephusCircle:
    """Josephus 문제를 원형 연결 리스트로 구현한 클래스"""

    def __init__(self):
        # 원형 연결 리스트의 시작 노드를 가리킵니다.
        self.head = None
        # 현재 탐색 중인 노드를 가리킵니다.
        self.current = None

    def initialize_circle(self, n: int):
        """
        n개의 노드를 가진 원형 연결 리스트를 초기화합니다.
        
        Args:
            n (int): 생성할 노드(사람)의 총 수.
        """
        if n <= 0:
            raise ValueError("노드 수(n)는 1 이상이어야 합니다.")

        # 첫 번째 노드를 생성하고, head와 current로 지정
        head_node = Node(1)
        self.head = head_node
        self.current = head_node

        # 2부터 n까지 노드를 생성하고 연결
        for num in range(2, n + 1):
            new_node = Node(num)
            self.current.next = new_node
            self.current = new_node

        # 원형 리스트를 만들기 위해 마지막 노드의 next를 head로 연결
        self.current.next = self.head

    def josephus_solution(self, k: int) -> str:
        """
        Josephus 문제를 해결하여 제거되는 순서를 반환합니다.
        
        Args:
            k (int): 제거할 순서(간격).
        
        Returns:
            str: 제거된 노드의 순서를 나타내는 문자열. 예) "<3, 6, 2, 7, 5, 1, 4>"
        """

        if self.head is None:
            raise ValueError("리스트가 초기화되지 않았습니다. 먼저 initialize_circle을 호출하세요.")
        if k <= 0:
            raise ValueError("간격(k)는 1 이상이어야 합니다.")

        result = []

        # 마지막 노드가 자기 자신을 가리킬 때까지 (노드가 하나 남을 때까지) 반복
        while self.current != self.current.next:
            # k-1번 이동: k번째 노드를 제거하기 위해 k-1번 next로 이동
            for _ in range(k - 1):
                self.current = self.current.next
            
            # k번째 노드 제거
            removed_node = self.current.next
            self.current.next = removed_node.next
            result.append(removed_node.data)

        # 마지막 남은 노드도 제거 대상에 포함
        result.append(self.current.data)

        # 요구하는 출력 형태로 포맷팅
        return "<" + ", ".join(map(str, result)) + ">"


def main():
    # 사용자 입력: n과 k
    n, k = map(int, input().split())

    # 원형 리스트 초기화 및 Josephus 문제 해답 출력
    circle = JosephusCircle()
    circle.initialize_circle(n)
    print(circle.josephus_solution(k))


if __name__ == "__main__":
    main()