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

1. 문제이해

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

2164번: 카드2

 

1 ~ N 까지의 숫자가 적힌 N장의 카드가 주어질 때,

다음과 같은 규칙을 적용 후, 마지막에 남는 카드에 적힌 숫자를 출력하는 것이 목표이다.

 

1. 제일 위에 있는 카드를 바닥에 버린다.

2. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

3. 다음과 같은 동작을 카드가 한 장 남을 때까지 반복한다.

 

 

 

2. 문제풀이

 

전형적인 큐(queue) 문제이다.

큐란, 후입선출 구조의 스택과는 달리 선입선출(FIFO) 구조를 가지는 자료구조이다.

제일 먼저 넣은 데이커가 가장 먼저 나오게 되며, 큐의 가장 앞을 front, 뒤를 back이라고 한다.

 

해당 문제에서는 자료구조인 큐를 이용해 제일 위(앞)에 있는 숫자를 버리고,

그 다음 제일 위에 있는 숫자를 제일 아래(뒤)로 옮겨주면 된다.

위 과정을 숫자가 1개가 남을 때까지 반복해주면 된다.

이를 코드로 정리해보면 다음과 같다.

 

// 큐에 마지막 원소 하나 남을때까지 아래 작업 반복
	while (q.size() != 1) {
		// 1. 맨 위 원소를 삭제
		q.pop();                

		// 2. 다음 위에 있는 원소를 가장 뒤에 대입
		q.push(q.front());

		// 3. 앞에 있는 원소 삭제(2, 3을 통해 원소가 뒤로 이동한 꼴)
		q.pop();                
	}

 

큐에 대한 보다 자세한 설명과 사용법은 이전에 포스팅한 적이 있으니,

아래 포스팅을 참고 바랍니다.😊

 

https://beginnerdeveloper-lit.tistory.com/35

[C++] 백준 10845번 큐

 

 

 

3. 소스코드

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

int main() {
	int N;
	queue <int> q;

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

	// 큐에 마지막 원소 하나 남을때까지 아래 작업 반복
	while (q.size() != 1) {
		// 1. 맨 위 원소를 삭제
		q.pop();                

		// 2. 다음 위에 있는 원소를 가장 뒤에 대입
		q.push(q.front());

		// 3. 앞에 있는 원소 삭제(2, 3을 통해 원소가 뒤로 이동한 꼴)
		q.pop();                
	}

	cout << q.front();

	return 0;
}

1 ~ N 까지의 숫자가 적힌 N 장의 카드를 입력받아, 큐에 숫자를 저장한다.

이후, 큐에 남은 숫자가 1개가 될때까지 위와 같은 작업을 반복하고,

마지막 남은 숫자를 출력한다.

 

주석없는 코드는 왼쪽 아래 더보기를 참고 바랍니다.😊

<주석 없는 코드>

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

int main() {
	int N;
	queue <int> q;

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

	while (q.size() != 1) {
		q.pop();                
		q.push(q.front());
		q.pop();                
	}

	cout << q.front();

	return 0;
}

 

 

---

문제에 대한 질문이나 지적은 언제나 감사하게 받고 있습니다.😊