조세퍼스 문제 : 어느 순서대로 제거되는지 출력해 보자.

 조세퍼스 문제는 다음과 같습니다. 시계 방향으로 1번부터 n번 사람이 있습니다. 처음에 k번째 사람을 뽑습니다. 뽑은 사람은 제거가 됩니다. 제거가 된 사람으로부터 k번 시계 방향으로 이동해서 있는 사람을 뽑습니다. 그 사람은 제거됩니다. 이런 식으로 n번 수행했을 때, 어떤 순서대로 제거되는지 구할 수 있을까요?

 

 예를 들어 n = 7이고 k = 3이라면, 3, 6, 2, 7, 5, 1, 4 순서대로 제거가 될 겁니다.

 

 

---

 나이브하게 풀었을 때, 주로 일어나는 연산은 2개입니다. 탐색, 삭제. List를 사용하면 배열에 비해 유리할 듯 싶습니다. 그렇지만, 탐색이 매우 많이 일어난다면 꼭 유리하다고 할 수도 없어요. k칸 이동을 O(1)만에 할 수 없기 때문입니다. 대신 배열은 랜덤 접근이 됩니다.

 

 따라서 배열 기반 자료구조인, vector를 사용해 볼 겁니다.

 

 

 먼저 벡터에 다음과 같이 초기화가 되어 있습니다. 편의상 0번부터 6번까지 시계 방향으로 있다고 해 볼게요. 그리고 n = 7, k = 3입니다. 처음에 3번째에 있는 것을 제거하라고 했기 때문에, v[2]에 있는 원소를 제거하면 좋겠네요.

 

 

 제가 초록색으로 칠한 부분입니다. 그 다음에 어떻게 하면 좋을까요? 일단 초록색으로 칠한 부분이 removed가 될 부분입니다. 그러니까, 왼쪽으로 1칸 이동합시다.

 

 

 그러면 보라색으로 가리키고 있는 위치가 기준점이 됩니다. 만약에 2가 제거가 되었다면, 이 보라색 위치로부터 시계 방향으로 3칸 이동하면 5가 있는 곳으로 이동할 겁니다.

 

 

 이 부분인가요? 즉, 우리는 v.begin() + 4로 이동하였습니다. 처음에 2번을 제거했을 때에는 v.begin() + 2를 가리켰는데요. 2를 제거하기 전에, 왼쪽으로 포인터를 1칸 이동시켰습니다. 다음에 그 위치로부터 3칸만큼 이동시켜야 하니까 우측으로 이동시킨 셈입니다. 즉, 제거한 위치 + (k - 1)의 값이 다음에 제거할 위치인 셈입니다.

 

 

 다음은 어떤가요? 5를 제거하려고 합니다. 그러면 똑같은 방식으로 해 봅시다. 일단 포인터를 왼쪽으로 1칸 이동시킵니다. 그러면, 포인터는 5가 아닌, 4를 가리킬 겁니다.

 

 

 즉, 보라색으로 칠한 부분을 가리킵니다. 이 때, 5를 remove 하면, 원소의 크기가 6이 아닌 5가 될 겁니다. 그리고, 현재 가리키고 있는 위치는 v.begin() + 3입니다. 이 상태에서 3칸을 이동해 볼 건데요. 3칸을 우측으로 이동하면, v.begin() + 6이 나올 겁니다.

 

 

 그런데, v.begin() + 6이면. 원소 크기가 5인데 v[6]. 뭔가 나머지 연산을 해 주어야 할 거 같지 않나요? 6%5의 값은 1입니다. 따라서, 실제로 3칸을 이동하면 1번째 원소를 가리키게 됩니다. 그림으로 봅시다.

 

 

 지금 보라색으로 칠한 위치를 가리키고 있어요. 이미 5는 제거된 상황이고요. 이 때, 우측으로 3칸만큼 이동하면 어떻게 되나요? +4, +0, +1이 됩니다. size가 5였고, 이동 전에 위치가 3이였는데요. (3+3)%5의 값이 1이기 때문에 최종적으로는 1번째 요소를 가리키게 된 셈입니다.

 

 

 그 다음에는 어떤가요? 일단 1번째 원소를 가리키고 있었는데요. 이 친구가 제거가 되어야 합니다. 그러면, pointer는 뒤로 1칸 후퇴합니다.

 

 

 그 다음에 어떻게 하면 좋을까요? 1번째 원소를 제거합니다. 그러니까 초록색으로 칠한 부분입니다. 그러면, 원소의 크기가 4가 될 건데요. 저는 0번째 원소부터 3칸을 움직였기 때문에, 최종적으로는 3번째 요소를 가리키게 됩니다.

 

 

 즉, 6이라고 써져 있는 것을 가리키게 된 셈입니다. 벡터는 삽입, 삭제가 O(n)이지만, 랜덤 접근이 가능하기 때문에, k만큼 이동하는 연산을 O(1)만에 할 수 있어요. 일반적인 List 같았으면, k번 이동하는데 O(k)만큼 걸렸을 겁니다. 스킵 리스트를 만들면 이야기가 달라지겠지만요.

 

 

---

 코드를 봅시다. 코드에는 1부터 n까지를 넣는데요. loc은 일단 0으로 초기화가 됩니다.

 

 

 그 다음이 문제인데, n이 1인 경우에는 그냥 <1>만 출력하면 됩니다. 그렇지 않은 경우에는 n번 loop를 돌면 되어요.

 

 

 코드에서 제일 핵심이 되는 부분은, cur_loc을 업데이트 하는 부분입니다. 1칸 뒤로 가고, m칸 앞으로 갔기 때문에, 현재 위치인 cur_loc에다가 (m-1)을 더합니다. 26번째 줄은 문제의 위치를 제거하는 연산인데요. iter가 가리키는 위치를 제거했다면, 사람 수가 하나 감소하기 때문에 sz를 하나 감소시키는 겁니다.