[C++] 백준 11866. 요세푸스 문제 0

문제

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

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 ≤ 1,000)

출력

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

구상 1

가장 처음 문제를 해결했던 방식이다. 

 

입력하는 개수만큼만 저장할 수 있도록 벡터를 선언하고 수를 넣는다.

vector <int> v;

for (int i = 1; i <= n; i++) {
	v.emplace_back(i);
}

예제처럼 n = 7, k = 3을 입력한다고 생각하자.

 

for (int i = 0; i < n; i++) {
	j += k;	//제거 대상
    if (j > n) j %= n;	//한 바퀴 돌았다는 뜻
	auto it = find(v.begin(), v.end(), j);	//제거 대상의 위치
	if (it != v.end()) {	//제거 대상이 존재할 때
		if (i != n - 1)	//마지막 반복이 아니면
			cout << v[it - v.begin()] << ", ";	//쉼표와 공백 추가 출력
		else cout << v[it - v.begin()];	//마지막 반복이면 숫자만 출력
		v.erase(it);	//제거
	}
}

순열에서 삭제할 번호를 의미하는 j를 선언한다.

k번째 사람을 계속 제거하므로 매 반복마다 j에다 k를 더해준다.

 

j가 n보다 커지면 벡터의 크기를 초과하게 된다.

j는 3, 6, 9로 증가한다. 9가 되면 처음 사람 수 7명보다 큰 번호가 존재하게 된다.

다시 첫 번째 요소로 돌아가기 위해서 처음 사람 수만큼 나눈 나머지 번호를 다시 j에 저장한다. 

9번은 없기 때문에 7 다음 다시 1로 돌아갈 수있게끔 나머지 연산을 하는 것이다.

j += k;	//제거 대상
  if (j > n) j %= n;	//한 바퀴 돌았다는 뜻

 

각 벡터에는 정수가 차례대로 저장되어 있다.

algorithm 헤더의 find() 함수를 이용해서 j번째 사람을 찾고, 그 원소가 담긴 주소 정보는 이터레이터 it에 저장한다.

auto it = find(v.begin(), v.end(), j);	//제거 대상의 위치

사람을 제거하기 전에 먼저 출력한다. 

출력 형식이

"<1, 2, 3... n>"과 같은 모양인데, 마지막 반복인 i = n - 1 일 때를 제외하고는 정수 뒤에 쉼표와 공백을 같이 출력해주고, 마지막 숫자는 그냥 출력해준다

if (it != v.end()) {	//제거 대상이 존재할 때
	if (i != n - 1)	//마지막 반복이 아니면
		cout << v[it - v.begin()] << ", ";	//쉼표와 공백 추가 출력
	else cout << v[it - v.begin()];	//마지막 반복이면 숫자만 출력

.

출력이 끝났으니 이제 숫자를 제거한다. 벡터 원소를 없애버려서 벡터의 크기는 1 줄어들게 된다.

v.erase(it);

 

 

그런데 이렇게 제거하다 보면 <3, 6, 2, 7>로 이어져야 할 결과가 <3, 6, 2, 5>가 된다.

3, 6, 2를 제거할 때는 이미 없어져서 건너뛰어야 하는 사람이 없었지만 다음 숫자를 제거할 때는 3과 6을 건너 뛰고 7을 제거해야 한다.

벡터에서는 3과 6이 사라졌지만 정수 체계에는 3과 6이 그대로 남아 있다. 우리가 앞서 j에다 k를 단순히 더했기 때문에 이런 결과가 나온 것이다. 

 

그래서 j를 증가시키는 구문을 수정해야 한다.

 

int j = 0;
for (int i = 0; i < n; i++) {
	for (int z = 0; z < k; z++) {
		j++;
		if (j > n) j %= n;	//다시 첫 번째로 복귀
		auto iter = find(v.begin(), v.end(), j);	//찾는 사람이 없으면
		if (iter == v.end()) z--;	//z를 1 감소시켜 찾을 때까지 한 번 더 반복시킴
	}
 }

j를 하나씩 증가시키면서 일일이 테스트해야 한다. 

z라는 변수를 하나 더 추가시킨다. k는 3으로 가정했으니 다음 세 번째 사람이 선택될 때까지 z를 증가시킨다.

for (int z = 0; z < k; z++) {

 

j를 일일이 하나씩 증가시키는데, 매 증가시킬 때마다 벡터 범위를 넘어갈 수 있으므로 확인해준다.

j++;
if (j > n) j %= n;	//다시 첫 번째로 복귀

 

 

find 함수를 이용해 원소를 찾고, 만약 원소가 이미 사라져서 벡터에 없다면 

z를 감소시켜 건너뛰었다는 것을 표시한다. 

auto iter = find(v.begin(), v.end(), j);	//찾는 사람이 없으면
if (iter == v.end()) z--;	//z를 1 감소시켜 찾을 때까지 한 번 더 반복시킴

 

 

코드1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	vector <int> v;

	for (int i = 1; i <= n; i++) {
		v.emplace_back(i);
	}
	cout << "<";
	int j = 0;
	for (int i = 0; i < n; i++) {
		for (int z = 0; z < k; z++) {
			j++;
			if (j > n) j %= n;	//다시 첫 번째로 복귀
			auto iter = find(v.begin(), v.end(), j);	//찾는 사람이 없으면
			if (iter == v.end()) z--;	//z를 1 감소시켜 찾을 때까지 한 번 더 반복시킴
		}
		j += k;
		if (j > n) j %= n;
		auto it = find(v.begin(), v.end(), j);
		if (it != v.end()) {
			if (i != n - 1)
				cout << v[it - v.begin()] << ", ";
			else cout << v[it - v.begin()];
			v.erase(it);
		}
	}
	cout << ">";

	return 0;
}

 

구상 2

요세푸스 문제는 꽤 널리 알려져 있는 문제인 듯 하다. 문제를 해결할 수 있는 다양한 방법이 이미 소개되어 있는데,

그 중에서 큐를 활용한 방법을 사용해보았다. 문제에서 시키는 그대로 실행하는 원형 연결 리스트를 일자로 편 형태다.

 

코드 2

#include <iostream>
#include <queue>

using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	cout << "<";
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < k; j++) {	//k-1번 동안 front 원소 옮기기
			q.push(q.front());
			q.pop();
		}
		if (i != n - 1)
			cout << q.front() << ", ";	//삭제 전 삭제하는 원소 출력
		else cout << q.front();
		q.pop();
	}

	cout << ">";

	return 0;
}

 

1.큐에 1부터 n까지 작은 수부터 순서대로 삽입한다.
2.다음을 n-1회 반복한다.
    k-1회 큐에서 수를 꺼낸 다음 곧바로 다시 삽입한다.
    큐에서 수를 하나 꺼낸다. 이 수가 다음으로 제거되는 수이며, 다시 삽입하지 않는다.
3.큐에 남아있는 수가 마지막에 남는 수이다.
사실상 연결리스트를 활용한 방법과 동일한 원리로 작동하므로 동일한 최적화 방식 역시 적용할 수 있고, 시간복잡도 역시 $\mathcal{O} \left( nk \right)O(nk)$이다.

나무위키 '요세푸스 문제' 바로가기