Linked List_BOJ #1158: 요세푸스 문제

문제

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

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)

출력

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

예제 입력 1

7 3

예제 출력 1

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

 

 

---

연결리스트를 이용한 방법

연결리스트와 배열 모두 데이터를 저장하기 위해 사용되지만
연결리스트는 배열과 같이 연속적인 메모리 위치에 저장되지 않고 포인터를 연결하는 구조이다.

새로운 요소를 삽입하거나 삭제할 때 공간을 만들고 기존 요소를 전부 이동해야하는 배열과 달리
연결리스트는 구조적 특징 덕분에 삽입/삭제가 용이하다.

그러나 특정 위치 자료의 탐색의 경우 배열이 더 용이하다.

 

 

요세푸스 순열 문제는 마지막 순서의 사람 다음에 다시 첫번째 순서의 사람으로 돌아가므로
원형 연결리스트를 구현하였다.

 

import sys
def input():
  return sys.stdin.readline().rstrip()

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

class CircularLinkedList:
  def __init__(self):
    self.head = Node('head')
    self.head.next = self.head
    self.cur_node = self.head
  
  def insert(self, item, new):
    new_node = Node(new)
    cur_node = self.find(item)
    new_node.next = cur_node.next
    cur_node.next = new_node

  def find(self, elem):
    cur_node = self.head
    while cur_node.element != elem:
      cur_node = cur_node.next
    return cur_node

  def find_prev(self, elem):
    cur_node = self.head
    while cur_node.next.element != elem:
      cur_node = cur_node.next
    return cur_node
  
  def remove(self, gap):
    cnt = 0
    while cnt < gap:
      self.cur_node = self.cur_node.next
      if self.cur_node.element != 'head':
        cnt += 1

    prev_node = self.find_prev(self.cur_node.element)
    prev_node.next = prev_node.next.next
    return str(self.cur_node.element)


# 입력
N, K = map(int, input().split())

# 원형 연결 리스트 생성
people_list = CircularLinkedList()
people_list.insert('head', 1)
for i in range(2, N+1):
  people_list.insert(i-1, i)

print("<", end="")
for i in range(N -1):
  print(people_list.remove(K), end=", ")
print(people_list.remove(K), end=">")

---

파이썬에서 print( )는 2개의 옵션을 사용 가능하다.

* sep=""

print문의 출력문들 사이에 원하는 문자를 넣을 수 있다.

default값은 공백이다.

>> print("첫번째","두번째","세번째")

첫번째 두번째 세번째

>> print("첫번째","두번째","세번째", sep="%sep%")

첫번째%sep%두번째%sep%세번째

 

* end=""

print문의 모든 출력 뒤에 원하는 내용을 설정할 수 있다.

default값은 개행(\n)이다.

>> print("첫번째 문장")
>> print("두번째 문장")

첫번째 문장
두번째 문장

>> print("첫번째 문장", end="$")
>> print("두번째 문장")

첫번째 문장$두번째 문장