백준 온라인 저지 | 1158번 요세푸스 문제 | C++

백준 온라인 저지 | 1158번 요세푸스 문제 | C++

1158번: 요세푸스 문제

 

1. 문제 정의

■ 1.1 요세푸스 순열

 요세푸스 순열은 1부터 N까지 숫자에서 K번째 숫자를 순서대로 없애는 순열을 말한다. 예를 들어, (7, 3) 요세푸스 순열은 1부터 7까지의 숫자에서 3번째 숫자를 순서대로 없애는 {3, 6, 2, 7, 5, 1, 4}이다.

 

■ 1.2 리스트

 요세푸스 알고리즘을 구현하려면 숫자를 넣고 빼내는 데 유용한 큐(queue) 혹은 리스트(list)를 사용하는 것이 적절하다. 나는 리스트를 사용하여 문제를 해결할 것이다.

 요세푸스 알고리즘은 다음과 같이 두 가지 방법으로 구현할 수 있다. 첫 번째 방법은 1부터 N까지의 숫자를 리스트에 담고 반복자(iterator)를 옮긴다. 이 방법은 반복자가 요세푸스 순열에 맞는 숫자를 찾아내면 숫자를 다른 컨테이너에 저장한다. 그런 다음, 이 숫자를 erase 메서드로 리스트에서 제외시키고 위의 과정을 반복한다. 두 번째 방법은 1부터 N까지의 숫자를 리스트에 담고 마치 원형 리스트처럼 처음 원소를 마지막 원소 뒤로 이동시킨다. 이 방법은 가장 첫 번째 원소가 요세푸스 순열에 해당하는 숫자면 이 숫자를 다른 컨테이너에 저장한다. 그리고 마찬가지로 리스트에서 pop_front 메서드로 빼내고 위의 과정을 반복한다. 나는 두 번째 방법으로 문제를 해결해보려고 한다.

 

2. 문제 풀이

■ 2.1 풀이 가이드: 리스트

1. 1부터 N까지의 숫자를 저장할 리스트 l과 요세푸스 순열을 저장할 벡터 v를 선언한다.
2. 리스트에서 첫 번째 원소를 가장 마지막 원소 뒤로 K번 옮긴다.
3. 이제 리스트의 첫 번째 원소는 요세푸스 숫자이므로 벡터에 저장한다. 그리고 리스트에서 이 숫자를 빼낸다.
4. 리스트가 빌 때까지 ②~③번 과정을 반복한다.
5. 요세푸스 순열이 저장된 벡터를 결과에 알맞게 출력한다.

 

■ 2.2 시간 복잡도와 공간 복잡도

 (N, K) 요세푸스 순열은 N개의 숫자에 대해서 K번 for문을 반복하여 첫 번째 원소를 마지막 원소 뒤로 옮기므로 시간 복잡도는 O(NK)이다.

 

3. 문제 해결

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// 요세푸스 (N, K)를 정의합니다.
	int N, K;
	cin >> N >> K;
	// 리스트를 선언하여 숫자 1부터 N까지 순서대로 저장합니다.
	list<int> l;
	for (int i = 1; i <= N; ++i) {
		l.push_back(i);
	}
	// 요세푸스 순열을 저장할 벡터를 선언합니다.
	vector<int> v;
	
	// 리스트가 빌 때까지 다음 요세푸스 알고리즘을 반복합니다.
	while (!l.empty()) {
		// 리스트 가장 처음 원소를 가장 마지막 원소 뒤로 K번 옮깁니다. 
		for (int j = 0; j < K - 1; ++j) {
			l.push_back(l.front());
			l.pop_front();
		}
		// 요세푸스 숫자를 벡터에 기록합니다.
		v.push_back(l.front());
		// 요세푸스 숫자를 리스트에서 빼냅니다.
		l.pop_front();
	}

	// 요세푸스 순열을 출력합니다. 
	cout << "<";
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		// 마지막 원소는 ", "를 출력하지 않습니다.
		if (i < v.size() - 1) {
			cout << ", ";
		}
	}
	cout << ">\n";
	return 0;
}

 

그림 1158번 요세푸스 문제 성공

 

4. 문제 고찰

■ 4.1 느낀 점

 큐 혹은 리스트로 구현할 수 있는 기본적인 요세푸스 순열에 대해 알아보았다. 이 문제는 반복자를 사용하지 않고 풀었지만, 다른 문제에서 반복자를 사용하는 경우가 많으므로 꼭 숙지하길 바란다.