[1158] 요세푸스 문제

---

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

1158번: 요세푸스 문제

요세푸스 순열을 queue를 활용하여 푸는 문제이다.

 

 

queue는 선입선출, 처음 넣었던 값이 제일 처음에 나온다는 뜻!

 

 

나 혼자 2시간 삽질하다가 다른 사람의 풀이를 참고하여 문제를 풀었다. ㅠㅠ

 

<처음에 삽질한 과정>

초반에는 queue가 아닌 deque를 사용하여 접근했다.

deque는 중간에서 데이터 삽입, 삭제가 가능했기 때문이다. (그래서 K번째 데이터를 삭제하려고 했음..)

queue에서 index로 데이터 삭제가 가능하다고 생각하고 문제를 풀었다.

그래서 

(cur + K - 1 + myqueue.size()) % myqueue.size();

꼴의 규칙을 발견했고, 이를 iterator를 움직이며 deque의 erase 함수를 쓰려고 했다.

 

하지만!

iterator erase (iterator position);

하지만 deque의 erase함수의 parameter는 자료형이 iterator였고,, iterator에서 % 연산자(나머지 연산자)는 사용할 수 없었다. ㅜㅜ

그래서 배열로 풀어보려 했으나 너무 복잡하여 포기..

 

 

<구글링을 통해 풀어낸 과정>

구글링을 통해 다른 멋진 사람들의 코드를 참고하여 문제를 다시 접근해보았다.

 

동그라미 친 부분이 출력, 빗금친 부분이 pop, 노란색은 push

queue로 push, pop을 이용하여 원하는 K번째 값을 빼내야 한다.

그러므로 K-1번 push, pop을 반복한다.

queue에서 push는 뒤에서, pop은 앞에서 실행된다. (한방향)

그 다음 front에 있는 값을 출력해주고 pop한다. (이러면 K번째 값이 튀어나와 보이는 것과 마찬가지)

 

그것을 반복해주면 되는데, 출력 형식에 따라 코드를 조금만 수정하면 된다.

그렇게 완성된 코드이다.

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

int N, K;
queue<int> myqueue;

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

	cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		myqueue.push(i + 1);
	}

	printf("<");
	while (!myqueue.empty()) {
		for (int i = 0; i < K - 1; i++) { // 뒤에 push한만큼 앞에서 pop
			myqueue.push(myqueue.front());
			myqueue.pop();
		}
		// 위의 for문 과정을 거치고 나면 K번째 수가 나옴
		if (myqueue.size() == 1) { // 맨 마지막 과정에선 출력 형식이 살짝 다름
			printf("%d>", myqueue.front());
		}
		else {
			printf("%d, ", myqueue.front()); // 출력 후
		}
		myqueue.pop(); // 없애줌
	}
}

 

자료구조 수강까지 했으면서 이런 거에 헤매는 나,,

공부할 수록 바보가 되어가는 기분이다