2- 6 보너스 요세푸스 문제

1. 현재 학습 진도

 링크드 리스트를 학습하고 있습니다

2. 어려움을 겪는 부분

• 보너스 문제인 요세푸스 문제를 '링크드 리스트'를 활용하여 푸는데 어려움을 겪고 있습니다 ㅠ  

3. 시도해보신 내용

• 링크드 리스트의 보너스 문제는 링크드 리스트를 학습하는데 도움이 될만한 문제라고 생각하여 풀이하고 있는데 어려움을 겪고 있습니다.

  
  

  
  
  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
  
  class CircularLinkedList:
      def __init__(self):
          self.head = None
  
      def append(self, data):
          new_node = Node(data)
          if not self.head:
              self.head = new_node
              self.head.next = self.head
          else:
              cur = self.head
              while cur.next != self.head:
                  cur = cur.next
              cur.next = new_node
              new_node.next = self.head
  
      def delete(self, prev, cur):
          if cur == self.head:
              if cur.next == self.head:  # 마지막 노드일 경우
                  self.head = None
              else:
                  self.head = cur.next
          prev.next = cur.next
  
      def print_all(self):
          if not self.head:
              return []
          result = []
          cur = self.head
          while True:
              result.append(cur.data)
              cur = cur.next
              if cur == self.head:
                  break
          return result
  
  def josephus_problem(n, k):
      circle = CircularLinkedList()
      for i in range(1, n + 1):
          circle.append(i)
  
      result = []
      cur = circle.head
      prev = None
  
      while circle.head:
          for _ in range(k - 1):
              prev = cur
              cur = cur.next
          result.append(cur.data)
          circle.delete(prev, cur)
          cur = prev.next if prev else None
  
      return result
  
  # 입력 처리
  n, k = map(int, input().split())
  result = josephus_problem(n, k)
  print("<" + ", ".join(map(str, result)) + ">")

  위와 같이 링크드 리스트의 개념을 활용하여 문제를 풀다가 어려워서 chatGPT의 도움을 받아서 변형하여 풀어봤는데도 지속적으로 런타임에러가 나는 상황입니다.

이 문제를 링크드리스트로 풀 수 없는 문제인지 어떤 부분이 잘못된 것인건지 잘모르겠습니다.

또한 만약 풀기 어려운 문제라면, 이정도 수준의 링크드 리스트를 활용하는 문제는 나오지 않는 것인지 이정도 수준으로 연습하면 좋을 지도 궁금합니다!

감사합니다 🙂