[백준 1158번 C++] 요세푸스 문제

1. 문제 링크

 

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

 

 

2. 문제 설명

N명의 사람이 원형으로 앉아있을 때 순서대로 K번째 사람을 제거하는 순서를 출력하는 문제입니다.

 

 

 

3. 소스코드

BOJ 1158번 요세푸스 문제 C++ 풀이입니다.

#include <iostream>
#include <vector>
using namespace std;
 
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
 
	int N, K, idx;
	cin >> N >> K;
	vector<int> v(N);
	idx = K - 1;
 
	for (int i = 0; i < N; i++) v[i] = i + 1;
	cout << '<';
	while (v.size() != 1) {
		cout << v[idx] << ", ";
		v.erase(v.begin() + idx);
		idx = (idx + K - 1) % v.size();
	}
	cout << v[0] << '>';
 
	return 0;
}

먼저 vector와 인덱스를 이용한 풀이입니다.

인덱스는 0부터 시작하므로 13번 라인에서 idx를 K - 1로 초기화했습니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 while문의 조건을 v.size() != 1로 설정했습니다.

먼저 idx에 있는 요소를 출력한 후, erase합니다.

idx를 K - 1만큼 증가시켰을 때, v의 범위를 초과하는 경우가 있으므로 size로 나눴을 때의 나머지를 대입합니다.

마지막으로 남은 요소를 출력하고 '>'를 같이 출력합니다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
 
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
 
	int N, K, idx;
	cin >> N >> K;
	vector<int> v(N);
	vector<int>::iterator t = v.begin();
	for (int i = 0; i < N; i++) v[i] = i + 1;
 
	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K - 1; j++)
			if (++t == v.end()) t = v.begin();
		cout << *t << ", ";
		t = v.erase(t);
		if (t == v.end()) t = v.begin();
	}
	cout << v[0] << '>';
 
	return 0;
}

vector와 iterator를 이용한 풀이입니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 바깥쪽 for문을 N - 1전까지만 돌게 설정했습니다.

vector와 index를 이용한 풀이처럼 while문의 조건을 v.size != 1로 설정해도 됩니다.

안쪽 for문은 K - 1번 돌면서 t를 한칸씩 이동시켜줍니다.

이 때 t가 end에 도달하면 v.begin()을 대입해줍니다. 원형이라고 생각하면 이해하기 쉽습니다.

현재 t위치의 요소를 출력한 후, 삭제(v.erase(t))를 해줍니다.

erase함수는 삭제한 요소의 다음 요소를 return하므로 이를 다시 t에 대입했습니다.

이 때 t가 end에 도달했을 경우 v.begin()을 대입해줍니다.

이 과정을 생략하면 안쪽 for문을 돌 때 ++t하는 과정에서 segmentation fault가 발생하므로 주의해야 합니다.

 

 

#include <iostream>
#include <list>
using namespace std;
 
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
 
	int N, K, idx;
	cin >> N >> K;
	list<int> l;
 
	for (int i = 0; i < N; i++) l.push_back(i + 1);
	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < K - 1; j++) {
			l.push_back(l.front());
			l.pop_front();
		}
		cout << l.front() << ", ";
		l.pop_front();
	}
	cout << l.front() << '>';
 
	return 0;
}

list 이용한 풀이입니다.

마지막 요소를 출력할 때는 ", "를 출력하지 않으므로 바깥쪽 for문을 N - 1전까지만 돌게 설정했습니다.

vector와 인덱스를 이용한 풀이처럼 while문의 조건을 l.size != 1로 설정해도 됩니다.

안쪽 for문은 K - 1번씩 돌면서 list의 맨 앞에 있는 요소를 맨 뒤로 옮겨줬습니다.

이를 구현하려면 맨 앞에 있는 요소(l.front())를 맨 뒤에 넣고(l.push_back), 맨 앞의 요소를 삭제(l.pop_front())하면 됩니다.

뒤로 다 옮긴 후 맨 앞에 있는 요소(l.front())를 출력한 후, 맨 앞의 요소를 삭제(l.pop_front())하면 됩니다.