백준 2346(풍선 터뜨리기) c++

문제

2346번: 풍선 터뜨리기

전에 풀었던 요세푸스 문제에서 응용한 문제 입니다. 요세푸는 문제는 오직 한방향으로만 원형으로 이동하지만

이 문제는 양쪽 방향으로 다 이동할 수 있습니다. 따라서 양쪽 원소에 접근할 수 있는 덱(deque) 자료구조를 

이용하였습니다.

---

int n;
cin >> n;

deque<pair<int,int>>d;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		d.push_back({ i + 1,k });
	}

풍선의 개수를 변수 n을 통해 입력받았습니다.

그 다음 덱을 선언했는데 자료형은 pair<int,int>형으로 받았습니다.

그래서 pair의 첫번째 원소는 풍선의 번호, 두번째 원소는 그 풍선이 가지고 있는 카드 숫자 라고 선언했습니다.

for문에서는 k를 입력받는데, k는 piar의 두번째 원소 즉, 풍선이 가지고 있는 카드 숫자입니다.

따라서 위의 코드를 실행시키면 덱 d는 풍선 1번부터 n번까지의 풍선이 쌓이게 됩니다.

while (!d.empty()) {
		int f, b;
		f = d.front().first;
		b = d.front().second;
		cout << f << ' ';
		d.pop_front();
		if (d.empty())
			break;
		if (b > 0) {
			for (int i = 0; i < b; i++) {
				d.push_back(d.front());
				d.pop_front();
			}
			d.push_front(d.back());
			d.pop_back();
		}
		else {
			for (int i = 0; i < -1 * b; i++) {
				d.push_front(d.back());
				d.pop_back();
			}
		}
	}

while절은 덱 d가 비워질때까지 반복합니다.

먼저 덱 d의 맨앞에 있는 원소를 추출해줍니다. 

따라서 변수 f에는 맨앞의 풍선의 번호, b에는 풍선에 쓰여진 숫자가 저장합니다.

그 다음 바로 풍선의 번호인 f를 출력해줍니다. 그 다음에 반복되는 풍선들도 맨앞에 위치시키고 풍선의 번호를 출력해주고 바로 제거하기 위함입니다.

그다음 덱이 비었는지 아닌지 확인할건데 이는 만약 마지막 풍선의 번호를 출력해주면 굳이 뒤에 있는 코드들을

실행 안해도 되므로 break하기 위함입니다.

만약 b(풍선의 쓰여진 번호)가 양수면 오른쪽으로 이동하고 음수면 왼쪽으로 이동하므로 서로 나누어 생각해줍니다.

---

전체 코드 입니다.

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;

	deque<pair<int,int>>d;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		d.push_back({ i + 1,k });
	}
	
	while (!d.empty()) {
		int f, b;
		f = d.front().first;
		b = d.front().second;
		cout << f << ' ';
		d.pop_front();
		if (d.empty())
			break;
		if (b > 0) {
			for (int i = 0; i < b; i++) {
				d.push_back(d.front());
				d.pop_front();
			}
			d.push_front(d.back());
			d.pop_back();
		}
		else {
			for (int i = 0; i < -1 * b; i++) {
				d.push_front(d.back());
				d.pop_back();
			}
		}
	}
	return 0;
}