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

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

해설

원형 큐 문제이다. 큐로 풀기에는 매우 까다롭고 덱큐를 사용해서 원형큐를 흉내 내어 풀어야한다.

종이에 적힌 수가 양수인 경우와 음수인 경우를 나누어서 생각해야한다.

양수인 경우 dq의 front를 dq의 back에 넣어주고 음수인 경우 dq의 back을 front에 넣어주면된다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>

using namespace std;
using ll = long long;
#define endl "\n"

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	deque<pair<int, int>> dq;
	int n;
	cin >> n;
	int num;
	for (int i = 0; i < n; ++i)
	{
		cin >> num;
		dq.push_back(make_pair(num, i + 1));
	}
	while (!dq.empty())
	{
		int cur = dq.front().first;	
		cout << dq.front().second << " ";
		dq.pop_front();

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

	return 0;
}

 

후기

dq의 특성을 활용할 수 있는지 없는지 물어보는 문제라고 생각한다.

한 번 풀고 나면 비슷한 문제들같은 경우 응용해서 풀 수 있을 것 같다.