문제

[BAEKJOON - 1158번: 요세푸스 문제]

풀이

큐를 활용하여 풀기

1. 1 부터 시작하여 1 씩 더해지는 N 개의 값을 큐에 넣어준다.
2. 큐에서 front 값을 pop 을 하여 다시 push 해 준다.
3. 이 때, K 번째에 pop 되는 값은 출력을 해주고, push 를 하지 않는다.
4. 큐가 빌 때 까지 반복한다.

소스 코드

#include <iostream>
#include <queue>

using namespace std;

void solution(int N, int K){
	int count;
	int value;
	queue<int> queue;

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

	count = 0;
	cout << "<";
	while(not queue.empty()){
		count += 1;
		value = queue.front();
		queue.pop();
		
		if(count % K == 0){
			cout << value;
			if(not queue.empty())
				cout << ", ";
		}
		else
			queue.push(value);	
	}
	cout << ">" << endl;
	
}

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

	solution(N, K);

	return 0;

}

피드백

아이디어

처음에 떠올린 아이디어는 원형 연결리스트를 구현하는 거였다.

이 방법으로도 물론 결과를 도출해 낼 수 있겠지만, 아직 코딩 실력이 부족한 본인으로서는, 이를 구현하는데에 상당히 애를 먹을 수 밖에 없었다.

더 단순하고 쉬운 해결법이 있을 수 있음을 기억하며, 무작정 문제에 달려들기 보다는, 다양한 해결방법을 생각해 보는 것이 필요하다는 것을 느꼈다.

출력

출력을 처음 구현할 때,

cout << "\b\b>" << endl;

이와 같은 코드로, < , , > 출력 형식의 마지막 콤마를 없애 주었으나,

답안을 제출하였을 때의 결과는 '틀렸습니다' 였다.

논리에 문제가 있는지 한참 생각해보고, 결국에는 다른 정답코드를 가져와, 케이스 들을 넣어보며 답안을 비교하였으나, 틀린점을 찾을 수 없었다.

결과적으로 출력을 \b 를 활용하지 않는 다른 방법으로 구현하자, 정답을 맞힐 수 있었다.

정확한 원인은 찾지 못하였으나, 논리적인 부분을 잘 구현한 것 같은데 계속 실패할 경우에는, 논리가 아닌 다른 부분에서 문제가 생겼을 수 있음을 알아야 한다는 점을 느꼈다.