백준 1158. 요세푸스 문제

큐의 대표적인 문제

요세푸스 문제

1. 간단 설명

---

N명이 원형 테이블에 앉아있을 때, K번째 되는 사람이 원형 테이블에서 나간다

모든 사람이 제거될 때 까지 반복할 때, 순서를 출력하는 문제

2. 문제 분석

---

큐를 이용한 풀이와, 연결리스트를 이용한 풀이 두가지로 풀어보았다

1. 원형큐를 이용한 풀이

여기선 std::queue를 이용

필요 변수

• 사람 수 N과, 몇번째 사람을 제거할건지 K를 int로 받는다 (1 ≤ K ≤ N ≤ 5,000)
• 사람들을 저장할 큐 std::queue qu;

알고리즘

1. N과 K를 입력받는다
2. 큐를 생성하고 1~N까지 삽입한다
3. 큐의 원소가 하나 남을때까지 다음 과정을 반복한다
	3-1. 큐의 맨 앞 원소를 꺼낸다
	3-2. 현재 차례가 K번째 원소가 아니라면, 다시 큐의 맨 뒤에 집어넣는다
	3-3. K번째 원소라면, 출력하고 다시 집어넣지 않는다(버림)
4. 3의 과정을 종료했다면, 원소가 하나만 남은것 이므로 이를 출력 후 종료한다

2. 연결리스트를 이용한 풀이

자료구조만 다르지 큰 알고리즘은 유사하다

std::list를 이용해 list를 선언하고,

C++ 리스트는 임의접근이 불가능하므로, iterator를 이용해 원소를 탐색한다

3. 소스코드

---

1. 큐를 이용한 풀이

#include <iostream>
#include <queue>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;

	queue<int> qu;
	for (int i = 1; i <= N; i++) {
		qu.push(i);
	}

	cout << "<";
	while (qu.size() > 1) {
		for (int i = 1; i < K; i++) {
			int now = qu.front();
			qu.pop();
			qu.push(now);
		}
		cout << qu.front() << ", ";
		qu.pop();
	}
	cout << qu.front() << ">";

	return 0;
}

2. 연결리스트를 이용한 풀이

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

int main() {

	int N, K;
	cin >> N >> K;

	list<int> li;
	for (int i = 1; i <= N; i++) 
		li.push_back(i);

	cout << '<';
	list<int>::iterator iter = li.begin(); // iterator

	int i = 1;

	while (!li.empty()) {
		if (i % K == 0) {
			cout << *iter;
			iter = li.erase(iter);
			cout << (li.empty() ? ">" : ", ");
		}
		else iter++;
		if (iter == li.end()) 
			iter = li.begin();
		i++;
	}
}

4. 배운점

---

C++ list를 사용하면서, 반복자 무효화 현상을 직접 다뤄볼 수 있었다

반복자 무효화 현상은,

반복자가 특정 원소를 가리키고 있었는데, 이를 삭제해버리면 더 이상 가리킬곳이 없어져버리는 현상이다

C++에서 iterator를 사용할 때 특히 주의해야한다

Visual Studio에서는 에러가 별도로 발생하지 않았으나, 백준에서 제출 시 런타임 에러가 발생한다

• iterator로 마지막 원소를 삭제하는 방법은 따로 없을까?

• iterator를 클래스처럼 delete 하는 방법은 따로 없을까?

더 찾아봐야할듯