[알고스팟] 조세푸스 문제(JOSEPHUS)

[알고스팟] 조세푸스 문제(JOSEPHUS)

목표 : 책 "알고리즘 문제 해결 전략 문제 풀이" 중 문제 조세푸스 문제(JOSEPHUS)를 풀어보자

문제 URL

풀이

조세푸스 문제는 대표적인 큐 시뮬레이션 문제입니다. 먼저 첫 번째 예제를 살펴보도록 할까요?

N = 6, K = 3

병사들은 1~6번까지, 원 형태로 앉아 있습니다. 이제 1번부터 2명이 남을 때까지 차례대로 죽여 나갈 건데, 아래 표에서 죽인다면, X를 표시해보도록 하지요. 또한, O는 죽어야 하는 놈을 가리키는 인덱스라고 하겠습니다.

1명 쨰,

| 1 | 2 | 3 | 4 | 5 | 6 |
| X |   |   |   |   |   |
| O |   |   |   |   |   |

1번은 안타깝게도 묻지도 따지지도 않고 죽여야 합니다.

2명 째,

| 1 | 2  | 3  | 4 | 5 | 6 |
| X |    |    | X |   |   |
|   | -> | -> | O |   |   |

1번으로부터 K=3 번쨰로부터 떨어진 병사 4번을 죽이는 것입니다.

3명 째,

| 1 | 2 | 3 | 4 | 5  | 6  |
| X | X |   | X |    |    |
|   | O |   |   | -> | -> |

이제 4번으로부터 3번째 떨어진 병사를 죽여야 합니다. 이 때, 죽은 병사를 고려하고 원형이라는 것을 고려해야만 합니다. 즉 O가 가리키는 인덱스는 5번 -> 6번 -> 2번이 된다는는 것을 알 수 있지요.

4명 째,

| 1 | 2 | 3  | 4 | 5  | 6 |
| X | X |    | X |    | X |
|   |   | -> |   | -> | O |

이제 남아 있는 병사 3, 5, 6 중에 2번에서부터 3번 째 떨어진 병사(3->5->6), 즉 6번을 죽이면 됩니다. 이제 3번 5번 2명이 남았으니 이것을 멈추면 됩니다. 이제 이것을 어떻게 쉽게 풀 수 있을까요? 쉽게 생각해볼 수 있는 것은 먼저 2개의 배열을 쓰는 방법이 있습니다. 근데 이러면, 병사들이 죽었는지 여부를 판단해서 인덱싱을 옮겨야 해서, 문제를 풀 때 고려해야 할 것이 많아집니다. 이것을 쉽게 푸는 포인트는 앞서 말했 듯이 큐를 이용하는 것이죠. 일단 알고리즘의 뼈대는 다음과 같습니다.

1. 큐에 1 ~ N까지 데이터를 넣습니다.
2. 큐에 2개가 남을 때까지 다음을 순회합니다.
   1. 데이터를 삭제합니다. (K번째)
   2. K-1번 큐의 맨 앞에 저장된 데이터를 맨 뒤로 보냅니다.
3. 2개의 데이터를 정렬시켜서 반환합니다.

마찬가지로 첫번 째 예제 입력 기준으로 이 알고리즘이 어떻게 되는지 동작으로 살펴보도록 하죠.

N = 6, K = 3

먼저 N 크기인 6, 1~6까지 큐에 데이터를 넣습니다.

q = [1, 2, 3, 4, 5, 6]

일단 1번은 묻지도 따지지도 않고 제거합니다. 큐는 다행히 pop이라는 연산을 통해서 가장 맨 처음 데이터를 제거할 수 있습니다.

q = [2, 3, 4, 5, 6]

이제 K-1번, 즉 2번 앞에 데이터를 맨 뒤로 보내줍니다. 이것은 front, pop, push 연산을 차례대로 적용하면 됩니다. 뒤에 코드를 보시면 금방 알 수 있을 겁니다.

q = [3, 4, 5, 6, 2] //1
q = [4, 5, 6, 2, 3] //2

이제 다시 반복문을 돌아, 맨 앞에 데이터, 즉 K(3)번째 병사를 죽이는 것이죠.

q = [4, 5, 6, 2]

이 과정을 데이터가 2개 남을 때까지 진행하면 됩니다. 반복 횟수에 따른 동작은 다음과 같습니다.

초기 상태

q = [1, 2, 3, 4, 5, 6] 

첫 번째

//1번 제거
q = [2, 3, 4, 5, 6]
//K-1번 데이터 이동
q = [3, 4, 5, 6, 2]
q = [4, 5, 6, 2, 3]

두 번째

//1번으로부터 K번 떨어진 4번 제거
q = [5, 6, 2, 3]
//K-1번 데이터 이동
q = [6, 2, 3, 5]
q = [2, 3, 5, 6]

세 번째

//4번으로부터 K번 떨어진 2번 제거
q= [3, 5, 6]
//K-1번 데이터 이동
q = [5, 6, 3]
q = [6, 3, 5]

네 번째

//2번으로부터 K번 떨어진 6번 제거
q = [3, 5]
//K-1번 데이터 이동
q = [5, 3]
q = [3, 5]

2명 남았으니 이 과정을 멈추면 되지요. 다만, 위 동작에서도 보시다시피 데이터를 이동하는 과정에서 큐의 정렬이 깨지게 됩니다. 따라서, 반환할 때는 이들을 정렬시켜주어야 한다는 것을 잊으면 안됩니다. 저의 코드는 다음과 같습니다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

vector<int> solution(int N, int K) {
    //살아남은 병사들의 번호를 오름차순으로 저장하는 정답 배열
    vector<int> answer;
    //큐 생성
    queue<int> q;
    //1. 큐에 1~N까지 병사 삽입
    for (int i = 1; i <= N; i++) {
    	q.push(i);
    }

    //2. 큐의 데이터가 2개가 될 때까지 다음을 반복
    while (q.size() > 2){
        //K번째 병사 사살
	q.pop();
        //K-1번 이동(큐의 맨 앞 -> 큐의 맨 뒤로)
	for (int i = 1; i < K; i++) {
	    int keep = q.front();
	    q.pop();
	    q.push(keep);
	}
    }
    //3. 큐에 남아있는 2개의 데이터 배열에 넣고 정렬
    answer = vector<int>{ q.front(), q.back() };
    sort(answer.begin(), answer.end());
    return answer;
}


int main() {
    int C;
    cin >> C;

    for (int i = 0; i < C; i++) {
	int N, K;
	cin >> N >> K;

	auto res = solution(N, K);

	for (const auto &r : res) {
	   cout << r << " ";
	}
	cout << endl;
    }

    return 0;
}