[백준/BOJ][C++] 2346번 풍선 터뜨리기

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

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

	int N;
	cin >> N;

	deque<int> ballonNum(N); // 풍선번호
	vector<int> paperNum(N); // 종이번호

	// 풍선번호와 종이번호 입력
	for (int i = 0; i < N; i++)
	{
		ballonNum[i] = i + 1; // 1 ~ N
		cin >> paperNum[i]; // 입력된 값
	}

	int nextMove = 0; // 다음으로 이동하는 칸 수

	// 풍선을 터뜨리는 순서대로 번호를 출력
	while (!ballonNum.empty())
	{
		if (nextMove >= 0)
		{
			// 오른쪽 이동(양수)
			for (int i = 1; i < nextMove; i++)
			{
				ballonNum.push_back(ballonNum.front()); // 맨 앞의 풍선을 맨 뒤로 옮김
				ballonNum.pop_front(); // 맨 앞의 풍선 삭제
			}

			// 현재 맨 앞 풍선의 번호 출력
			cout << ballonNum.front() << " ";

			// 맨 앞의 풍선의 번호에 따라 다음 이동 칸 수가 정해짐
			nextMove = paperNum[ballonNum.front() - 1];

			// 풍선 터뜨리기 -> 덱에서 삭제
			ballonNum.pop_front();
		}
		else
		{
			// 왼쪽 이동(음수)
			for (int i = 1; i < -nextMove; i++)
			{
				ballonNum.push_front(ballonNum.back()); // 맨 뒤의 풍선을 맨 앞으로 옮김
				ballonNum.pop_back(); // 맨 뒤의 풍선 삭제
			}

			// 현재 맨 뒤 풍선의 번호 출력
			cout << ballonNum.back() << " ";

			// 맨 뒤의 풍선의 번호에 따라 다음 이동 칸 수가 정해짐
			nextMove = paperNum[ballonNum.back() - 1];

			// 풍선 터뜨리기 -> 덱에서 삭제
			ballonNum.pop_back();
		}
	}

	return 0;
}

---

<풀이과정>

1. N을 입력받고, 풍선의 번호(이하 풍선번호)를 나타낼 덱 ballonNum과 풍선 속 종이의 번호(이하 종이번호)를 나타낼 벡터 paperNum을 각각 N의 크기로 초기화하여 선언해준다.

2. 0부터 N까지 반복하며 ballonNum은 1부터 차례로 넣어주고, 입력받은 값을 paperNum에 차례로 넣어준다.

3. 다음 이동해야하는 칸 수를 나타내는 int형 변수 nextMove를 선언하고 처음에는 1번부터 움직이지 않고 터뜨리므로 0으로 초기화 해 준다.

4. nextMove가 양수인 경우 오른쪽으로 이동하므로 1부터 nextMove -1 까지 반복하며 맨 앞의 풍선을 맨 뒤로 보내는 과정을 진행하여 반복이 끝나면 맨 앞에 터뜨릴 풍선이 오게 한다.

5. 반복이 끝난 뒤 맨 앞의 풍선번호를 출력하고, 해당 번호를 이용해 paperNum에 접근하여 nextMove값을 해당 풍선 속 종이번호로 바꿔준다.

6. 마지막으로 맨 앞의 풍선은 사용된 풍선이므로 덱에서 삭제한다.(풍선을 터뜨리는 작업)

7. 음수인 경우 양수와는 반대로 맨 뒤의 풍선을 맨 앞으로 보내는 과정을 반복하여 맨 뒤에 풍선이 오게하고, 해당 풍선을 터뜨리는 과정을 진행한다.

8. 위의 과정을 풍선번호 ballonNum이 빌 때까지 반복하여 풍선을 터뜨리는 순서를 찾아낼 수 있다.

---

<코멘트>

이 문제는 어떻게 푸는지 생각해내는게 어려웠다.

풍선의 번호와 풍선 속 종이의 번호를 구분하여 생각하는 것과 덱을 이용해 하나씩 앞 또는 뒤로 보내면서 덱을 유지시키며 해당 풍선을 찾아내는 것이 관건이었다!

---

<제출결과>