[백준/BOJ][C++] 2164번 카드2

<문제 소개>

---

<소스 코드>

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

void Shuffle(queue<int>& q)
{
	q.pop(); // 맨 위의 카드를 버림
	q.push(q.front()); // 그 다음 맨 위의 카드를 밑으로 옮김
	q.pop(); // 옮긴 카드를 버림
}

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	queue<int> q;

	// 1부터 N까지 수를 큐에 담음
	for (int i = 1; i <= N; i++)
	{
		q.push(i);
	}

	while (q.size() != 1)
	{
		Shuffle(q);
	}
	
	cout << q.front();

	return 0;
}

---

<풀이과정>

1. STL의 queue를 이용해 q를 선언

2. 1부터 N까지 반복하며 q에 해당 수들을 차례로 담음

3. q의 크기가 1이될 때까지 shuffle 함수 반복 진행

4. q의 맨 앞의 원소를 출력

 

- Shuffle

1. 인자로 queue의 주소값을 받아와서 함수 종료 이후에도 q가 해당 값을 유지하게 함

2. 맨 위의 카드를 버리는 작업인 pop을 진행

3. 그 다음 맨 위의 카드를 밑으로 옮기기 위해 front를 이용해 q의 현재 맨 앞 원소에 접근하고 해당 원소를 push를 이용해 q의 맨 뒤에 넣어준다.

4. 넣어준 원소는 옮긴 카드에 해당되고 카드는 이미 옮겨졌으므로 해당 카드를 버리기 위해 pop을 한번더 진행한다.

---

<코멘트>

큐를 이용해 간단하게 풀어보았다!

---

<제출결과>