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

문제 링크

2346번: 풍선 터뜨리기

문제 요약

N개의 풍선이 주어지고, 풍선 안에는 종이가 적혀 있다. 1번 풍선부터 시작해서 풍선을 터뜨리는데, 풍선 안의 종이에 적힌 숫자만큼 이동한 뒤에 풍선을 터뜨린다. 이때 터지는 풍선의 순서를 출력해야 한다.

접근 방법

N이 1000 정도이고, 2초나 주어지기 때문에, 한 칸씩 이동하는 것을 직접 시뮬레이션 돌려도 무방합니다.

풍선 안에 들어있는 종이의 숫자는 음수도 가능하기 때문에, 양방향으로 회전시킬 수 있는 자료 구조가 필요합니다. 그래서 양쪽으로 삽입, 삭제가 가능한 덱을 사용해서 풀었습니다.

다음 반복에서 덱의 front의 원소를 무조건 삭제할 것이기 때문에 오른쪽으로 이동할 때는 (적힌 숫자 - 1)회 이동해야 하고, 왼쪽으로 이동할 때는 (적힌 숫자)회 이동해야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

deque<pair<int, int>> dq;

int main(void)
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		dq.push_back({ num, i + 1 });
	}

	while (1)
	{
		pair<int, int> now = dq.front();
		dq.pop_front();
		cout << now.second << ' ';

		if (dq.empty())
			break;

		if (now.first > 0)
		{
			for (int i = 0; i < now.first - 1; i++)
			{
				dq.push_back(dq.front());
				dq.pop_front();
			}
		}
		else
		{
			for (int i = 0; i < -now.first; i++)
			{
				dq.push_front(dq.back());
				dq.pop_back();
			}
		}
	}

	return 0;
}