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

풀이 문제 : 백준 1158번 요세푸스 문제
풀이 언어 : C++
알고리즘 : queue
문제링크 : https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

문제요약

---

원으로 이어진 배열에서 돌아가며 k번째 수를 제거하고, 제거한 순서대로 출력하는 문제다.

 

접근 방식

---

처음엔 구현문제 처럼 풀었다. while 문으로 숫자를 점점 키우면서 k번째가 되면 정답배열에 넣고, used 배열(visited 배열) 에 사용 표시를 하는 식으로 구현했다.
정답은 맞았지만 풀면서 약간 갸우뚱해서 구현 후 정답 코드를 봤다. queue를 이용해 k만큼 돌면서 pop과 push를 반복하고, k번째에서 pop 하는 형식이었다. 이 방식이 훨씬 구현하기 편하고 간단하다.

또 이 문제에서 특이한 점은 출력 형식이다. <>와 ,를 이용하기 때문에 마지막 수를 출력할때는 반복문 밖에서 따로 출력해주어야한다.

 

코드

---

처음에 푼 방식

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

int n, k;
int now = 1;
int cnt = 1;
int endCnt;
int used[5001];
vector<int> answer;

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

	cin >> n >> k;
	while (1) {
		if (used[now] == 1) {
		}
		else {
			if (cnt == k) {
				answer.push_back(now);
				endCnt++;
				used[now] = 1;
				cnt = 1;
			}
			else {
				cnt++;
			}
		}
		// 마무리 (다음을 위해)
		now++;
		if (now == n+1) now = 1;
		if (endCnt == n) break;
	}
	cout << "<";
	for (int i = 0; i < n-1; i++) {
		cout << answer[i] << ", ";
	}
	cout << answer[n - 1];
	cout << ">";
	return 0;
}

 

queue 이용한 방식

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

int n, k;
queue<int> q;

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

	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		q.push(i + 1);
	}

	cout << "<";
	while (q.size() > 1) {
		for (int i = 0; i < k - 1; i++) {
			int temp = q.front();
			q.push(temp);
			q.pop();
		}
		cout << q.front()<<", ";
		q.pop();
	}
	cout << q.front();
	cout << ">";
	return 0;
}

 

queue를 이용한 방식이 훨씬 빠르기도 했다.

(위) queue 이용, (아래) 구현

 

회고

---

queue의 FIFO 특징을 활용해 pop과 push를 반복하여 원하는 수를 찾을때까지 돌려볼 수 있다는 걸 알았다.
또한 출력형식이 이 문제처럼 특이할 경우 queue size 를 확인하여 마지막 수를 반복문 밖에서 출력하면 된다.