백준 2346번: 풍선 터뜨리기 (C++)

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

2346번: 풍선 터뜨리기

 

풀이

직접 구상하진 않고 친구에게 들은 방식으로 구현했다.

덱 자료구조를 사용해서 원형 큐 처럼 구현하면 된다고 들었다.

 

우선, 가장 앞에 있는 풍선의 값만큼 이동한다.

그 값이 양수라면, 앞에 있는 것들을 뒤로 붙여주고

음수라면 뒤에있는 것들을 앞에 붙인다.

 

즉, 양수일 때  ->  push_back(front())  ->  pop_front()

음수일 때  ->  push_front(back())  ->  pop_back()

전체 코드

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	deque<pair<int, int>> deq;

	cin >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		deq.push_back({ a, i + 1 });
	}

	for (int i = 0; i < N - 1; i++) {
		cout << deq.front().second << ' ';
		int tmp = deq.front().first;
		if (tmp > 0) {
			deq.pop_front();
			for (int j = 0; j < tmp - 1; j++) {
				deq.push_back(deq.front());
				deq.pop_front();
			}
		}
		else {
			deq.pop_front();
			for (int j = 0; j < abs(tmp); j++) {
				deq.push_front(deq.back());
				deq.pop_back();
			}
		}
	}
	cout << deq.front().second << ' ';
}