6. 요세푸스 문제 (원형 연결 리스트, 파이썬)

요세푸스 문제(Josephus problem) 
혹은 요세푸스 순열(Josephus permutation)

 

전설에 의하면 1세기에 유대인 로마 전쟁 당시 역사가 플라비우스 요세푸스와 40명의 유대인이 로마 군인에게 붙잡힐 위기에 처했다.
유대인 병사들은 포로로 잡히느니 죽음을 택하기로 했다. 
사람으로 원을 만든 다음 사람이 남지 않을 때까지 매 세번째 병사를 죽여나가기로 작전을 세웠다.
요세푸스와 다른 한명은 일찍 죽음을 당하는 위치에 서고 싶지 않아 어디에 서야 최후까지 생존할 수 있을 지 빨리 계산해야 했다.
n명의 사람이 원을 만들고 매 m번째 사람을 죽이는 프로그램을 구현하시오.
그리고 마지막으로 남을 두 사람을 계산하시오.

 

리스트

먼저 리스트를 이용해 보겠습니다. 
(문제를 보고 처음 떠오른 거라..)

 

1. 리스트에 1부터 40까지 넣어준 뒤에 
2. 3번째 숫자인 3, 6, 9...  요소를 삭제합니다. 
3. 이를 위해 idx 변수를 쓰는데
4. 다음 요소를 찾기 위해 3을 더해준 뒤, 
5. 요소의 삭제와 함께 인덱스 1을 빼주는 게 포인트입니다. 
6. idx 변수의 값이 배열의 길이(에서 -1한 값) 보다 커지면 안되겠죠?
   배열의 길이보다 커지면 배열의 길이만큼 빼줍니다.

 

def josephus(m, n):
    s_list = [i for i in range(1, n+1)]
    idx = -1
    while len(s_list) > 2:
        idx += m
        if idx > len(s_list) - 1:
            idx -= len(s_list)
        del s_list[idx]
        idx -= 1
    return s_list


remains = josephus(3, 40)
print(remains)

#[13, 28]

 

원형(순환형) 연결 리스트

기존 원형 연결 리스트를 활용해서 만들어 보겠습니다.
https://comdoc.tistory.com/entry/%EC%9B%90%ED%98%95-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8Circular-linked-list-ADT-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

1. current에 현재 노드를 저장합니다. 초기 값은 head
2. find_next 함수(메서드)를 만들어 current를 다음으로 보냅니다. 
3. find_next 함수(메서드) 실행시 head 노드를 만나면 건너뛰게 합니다. 

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.current = self.head

    def insert(self, new):
        new_node = Node(new)
        new_node.next = self.head
        self.current.next = new_node
        self.current = new_node

    def find_next(self, n):
        for _ in range(n):
            if self.current.next.element == 'head':
                self.current = self.current.next
            self.current = self.current.next

    def remove(self, node):
        prev_node = self.head
        while prev_node.next != node:
            prev_node = prev_node.next
        prev_node.next = prev_node.next.next

    def show(self):
        cur_node = self.head
        while cur_node.next.element != 'head':
            print(cur_node.element, end=' -> ')
            cur_node = cur_node.next
        print(cur_node.element)


def josephus(m, n):
    boo = CircularLinkedList()
    for i in range(1, n + 1):
        boo.insert(i)
    # boo.show()
    for _ in range(n - 2):
        boo.find_next(m)
        boo.remove(boo.current)
    boo.show()


josephus(3, 40)

# head -> 13 -> 28

for 문, 언패킹 등에서 사용하지 않는 변수는 _ 를 사용하는 관례가 있습니다.