백준/2164/자료구조(큐)/카드2

백준/2164/자료구조(큐)/카드2

문제 해석

맨 위에 카드는 제외 그 다음 카드는 맨 아래로 옮기다가 카드숫자가 1개가 되었을 때 남는 카드를 확인하는 문제입니다.

문제 풀이

말 그대로 삽입과 삭제가 다른곳에서 일어나는 자료구조를 사용하는 알고리즘입니다.
저는 자료구조 중 큐 자료구조를 사용하였습니다.

카드의 사이즈가 1이 될 때까지 문제 해석의 쓰여있는 과정을 되풀이합니다.

if (cards.size() != 1)
	{
		while (true)
		{
			int card = cards.front(); cards.pop();
			if (cards.size() == 1)
				break;

			card = cards.front(); cards.pop();
			cards.push(card);
		}
	}

이 때 제 코드 같은 경우 카드 사이즈가 1일 때에는 반복문에서 하나남은 카드 마저 버려버리고 값을 출력하기에 데이터가 제로인 queue를 건들여 segmentation error가 발생했습니다. 이를 방지하기 위해 카드 사이즈가 1이 아닐때 (조건이 1<=N 이기 때문)에만 해당 과정을 진행하도록 했습니다.

풀이

첫번째 풀이(메모리 참조 오류)

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

queue<int>cards;

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

	int N = 0;
	cin >> N;

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

	
	while (true)
	{
		int card = cards.front(); cards.pop();
		if (cards.size() == 1)
			break;

		card = cards.front(); cards.pop();
		cards.push(card);
	}
	
	int result = cards.front();

	cout << result;

	return 0;
}

두번째 풀이

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

queue<int>cards;

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

	int N = 0;
	cin >> N;

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

	if (cards.size() != 1)
	{
		while (true)
		{
			int card = cards.front(); cards.pop();
			if (cards.size() == 1)
				break;

			card = cards.front(); cards.pop();
			cards.push(card);
		}
	}
	
	int result = cards.front();

	cout << result;

	return 0;
}