[BOJ] 1158번 요세푸스 문제

[BOJ] 1158번 요세푸스 문제 문제

자료구조 문제 중에서 굉장히 훌륭한 문제로 평가받는 문제다. 이 문제를 단순히 자료구조의 입장에서 풀지 않고, 쉬운 방법부터 시작해서 이를 자료구조로 이어지게 하는 풀이로 풀어보고자 한다.

---

이 문제는 원을 따라서 계속 사람을 뽑아내는 문제다. 남은 사람들에 한하여 $K$번째 사람이 뽑히고, 한번 뽑힌 사람이라면 그 사람은 제외되는 시스템을 가지고 있다.

만약 이 문제를 처음으로 맞닥뜨렸다면 우선 아래의 구현 문제점을 생각해 볼 수 있다. 편의상 문제의 예시와 같이 $N=7,K=3$이라고 하자. 

1. 어떻게 첫 $K$번째 사람을 찾을 것인가
2. 뽑힌 것을 어떻게 처리할 것인가
3. 여러 번 뽑힌 이후로는 어떻게 $K$번째 사람을 찾을 수 있는가

일단 하나씩 파헤쳐보자.

 

1. 어떻게 첫 $K$번째 사람을 찾을 것인가

이 부분은 배열을 배웠다면 쉽게 구현할 수 있을 것이다. 먼저 배열을 만든 후, $K$번째 index를 고르면 된다. 이렇게 해서 3, 6, 2를 뽑을 수 있다. 마지막에 2가 뽑히는 이유는 사람들이 원형으로 앉아 있음을 생각한다면 떠올리는 것이 어렵지 않을 것이다.

1. 어떻게 첫 K번째 사람을 찾을 것인가

 

2. 뽑힌 것을 어떻게 처리할 것인가 & 3. 여러 번 뽑힌 이후로는 어떻게 $K$번째 사람을 찾을 수 있는가

문제는 여기서부터 시작된다. 다음 것을 뽑아야 하는데 이미 뽑힌 사람들이 있기 때문에 이를 처리할 방법이 필요하다. 이는 또 다른 배열을 이용하여 처리한다. 뽑혔는지 안 뽑혔는지를 True 또는 False로 처리하여, True인 사람을 3번 지나칠 때까지 이 7명의 배열을 계속 돌린다. 마지막으로 모두 뽑힌 것이 확인될 때, 알고리즘이 종료된다.

2. 뽑힌 것을 어떻게 처리할 것인가 & 3. 여러 번 뽑힌 이후로는 어떻게 K번째 사람을 찾을 수 있는가

---

이 방법은 확실히 풀 수 있는 방법이지만, 너무나도 복잡하다는 단점이 존재한다. 즉, 원형으로 앉아있기 때문에 사용되는 나머지 연산인 $mod$를 한 번이라도 잘못 까딱하는 순간 이 문제는 정말 알 수 없는 미궁에 빠져버리게 된다. 즉, 이렇게 풀기 위해선 변수 컨트롤이 매우 중요하다.

하지만 이러한 방법을 쉽게 풀 수 있는 자료구조가 있으니, 바로 큐(Queue)다. FIFO(First In First Out)의 방식을 따르는 자료구조로써, 리스트에 처음 들어간 데이터가 가장 먼저 나오는 자료구조다. 처음 빨려진 음료가 가장 먼저 입으로 도착하는 빨대를 생각하면 쉽다.

이 문제를 queue를 이용해서 다시 풀어본다면 아래와 같이 풀 수 있다.

큐로 푸는 방법

$K$번째가 될 때까지 뽑은(Pop) 것을 다시 넣고(Push), $K$번째 회전이 되었을 때 나온 값을 뽑아가면 된다. 위의 그림으로 전부 설명이 가능하며, 위의 배열이 남지 않을 때까지 계속 돌리면 된다.

기존의 방법과는 달리 하나의 배열에서 모든 연산이 끝나며, 더욱더 직관적으로 풀이가 와닿음을 볼 수 있다. 그러나 푸는 방법은 사실상 처음의 접근법과 같다고 보면 된다!

---

import sys
from collections import deque

if __name__ == '__main__':
    N, K = map(int,sys.stdin.readline().rstrip().split())
    now_queue = deque(list(range(1, N+1)))
    josephus_list = list()

    while now_queue:
        for _ in range(K-1):
            now_queue.append(now_queue.popleft())
        # now_queue.rotate(-(K-1))
        josephus_list.append(now_queue.popleft())

    print('<', ', '.join(str(i) for i in josephus_list), '>', sep='')

파이썬에서는 큐를 나타내는 자료구조를 collections 패키지의 deque를 통해 사용할 수 있다. 물론 queue를 직접 구현하는 방법이 있지만 만약 queue라는 구조를 알기 위해 한 번 구현해 봤다면 굳이 그럴 필요까진 없다.

우리는 queue를 써야하므로 popleft & append 또는 pop & appendleft 둘 중 하나를 써야 한다. 이유는 queue는 단방향성을 가지기 때문이다. 개인적으로는 queue로 쓸 때 popleft & append를 사용한다. 여담으로 deque는 단어에서 de가 말하는 의미에서 보듯 양방향성 queue다.

$K$번째 사람을 구하기 위해 $K-1$번을 회전시킨 후 나온 마지막 값을 뽑아낸다. 회전을 하는 방법으로는 두 가지가 있는데, 하나는 popleft 한 것을 다시 append 하는 법, 그리고 다른 하나는 rotate라는 method를 쓰는 법이다. 이 방법들은 코드에 동시에 기재해 뒀으며, 둘 다 같은 행동을 하지만 rotate가 더 빠름을 알아두면 좋다.