[백준/C++]#1158 - 요세푸스 문제

풀이

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

int main() {
	int n,k,i;
	cin >> n;
	queue<int> s;
	for (int i=1; i<=n; i++) {		// 1~n의 숫자를 차례로 큐에 넣어줌
		s.push(i);
	}
	cout << "<";
	cin >> k;
	i = 1;
	while (n-1) {			// n-1이 0이 될 때까지 반복문 수행
		
		if (i % k != 0) {		// i 나누기 k의 나머지가 0이 아닐 때 front 값을 다시 큐에 넣고 pop
			s.push(s.front());
			s.pop();
		}
		else {				// i 나누기 k의 나머지가 0일 때 front 값을 출력하고 pop
			cout << s.front() << ", ";
			s.pop();
			n--;				// 빼는 시행마다 n을 1 제거
		}
		i++;			// 반복의 수만큼 i++;
	}
	cout << s.front() << ">";		// 마지막에 큐에 남은 값 출력
	return 0;
}

C++ 개념

이번에는 C++ STL의 queue 라이브러리를 사용했다. 큐는 FIFO의 특징을 가진다.

기본함수는 push(), pop(), front(), back(), empty(), size() 등이다.

스택과 다른 차이점으로는, front와 back의 값 모두 O(1)의 시간복잡도로 접근할 수 있다.

---

풀이

 

이번 문제에서는 원을 이루며 사람이 앉아 있다. 이러한 상황에서는 원형 큐가 유용하다.

일단 처음에 n을 입력받아서, 1~n을 차례로 큐에 저장했다.

그리고 k를 입력 받은 뒤, 반복문 안에서 if문으로 case를 나눈다.

k번째에서 값을 출력하고, 값은 사라지므로 k번째와 k번째가 아닌 상태를 나눴다.

k번째가 아닐 때는 front의 값을 push하고 pop을 한다.

+a

 

반복문을 n번으로 잡았더니, <3, 6, >에서 출력이 끝나게 됐다. 시행횟수는 n번이 아니라, 모든 성분이 다 큐에서 빠져나올 때까지이므로, 반복조건을 n이 0이 아닐 때로 수정했다.

 

이 경우 출력은 <3, 6, 2, 7, 5, 1, 4, >이 된다. 마지막 출력은 형태를 바꿔야하므로 반복조건에서 n을 n-1로 바꿨다.

큐에 성분이 하나 남았을 때, pop()하는 과정은 출력에 무관하므로 따로 시행하지 않았다.