[C++] 백준 2346번 : 풍선 터뜨리기 && deque에 대하여

출처 : https://www.codingninjas.com/studio/library/difference-between-queue-and-deque-in-c

• Def : "Doulbe-Ended Queue"라는 의미로, 큐와 비슷하나, 삽입과 삭제 부분이 정해진 queue와 달리, 양 방향으로 삽입 삭제가 가능해진 구조이다. 시내버스같은 구조로, 사람들이 많으면 버스도 앞문 뒷문 구분 없이 막 내리지 않는가. 그와 비슷한 것 같다. deck(갑판)이 아니다.
• Functions to use : push_front, push_back, empty, front, back, size etc.
  • push_back(x) : 덱의 가장 윗 데이터에 메모리를 생성, 데이터 x를 넣는다.
  • push_front(x) : 덱의 가장 아래 데이터에 메모리를 생성, 데이터 x를 넣는다.
  • pop_back() : 덱의 가장 마지막에(최근에) 입력된 데이터를 삭제한다. 덱가 비었다면 연산 정의 불가상태(error 발생)가 된다.
  • pop_front : 덱의 가장 처음에(오래 전에) 입력된 데이터를 삭제한다. 덱이 비었다면 연산 정의 불가상태(error 발생)가 된다.
  • empty() : 덱이 비었다면 1을 return하고, 그렇지 않다면 0을 반환한다.
  • front() : 덱의 가장 처음에(오래 전에) 입력된 데이터를 반환한다. 덱이 비었다면 연산 정의 불가상태(error 발생)가 된다. cf) stack의 경우, bottom()에 해당하는 함수인 것이다.
  • back() : 덱의 가장 마지막에(최근에) 입력된 데이터(가장 처음 저장된 값)를 반환한다. cf) stack의 경우,top()에 해당하는 함수인 것이다.
  • size() : 덱의 길이를 return해준다. 덱이 비었다면 연산 정의 불가상태(error 발생)가 된다.
  • emplace(x) : push(x)와 결과적으론 같은 것을 수행하지만, 연산속도가 더 빠르다.
    push() : 입력받는 값의 복사본을 덱의 마지막에 저장.(복사본 생성 -> 큐에 저장)
    emplace() : 입력받는 값 자체를 덱의 마지막에 저장,(큐에 저장)
    누군가의 속도 측정 결과, int type에선 emplace가 유리했지만, 이 외에선 비슷했다고 한다.
  • a.swap(b) : a와 b라는 덱을 동적으로 바꿔준다. 주소까지 바뀐다.(예시 : 직전 포스트 참고)
  • etc. 디게 많음 Ref부분의 c++공식 사이트 참고.
• How to make : pointer객체를 가지는 queue란 class를 만들고, 각각의 함수를 구현해주면 된다. 사실 다른 분들 거 코드를 봤는데 어려워서 STL을 사용했다. 조금 더 공부가 필요하다...
• How to use :  이미 만들어져 있어서, 그냥 #include <deque> 이후에  deque<자료형> 변수명 형태로 만들면 된다.
  - deque<자료형> dq(10) : 10개의 원소를 가진 deque 생성(default value : 0)
  - deque<자료형> dq(10,n) : value가 n인 10개의 원소를 가진 deque 생성
  - deque<자료형> dq1(dq2) : dq2를 복사한 dq1을 생성(복사 생성자)
• Advantage : 새로운 원소 추가시, 메모리 재할당 후 이전 원소를 복사하는 vector와 달리, 일정한 크기의 새로운 메모리 블록을 할당하는 배열기반의 구조를 사용함으로써 삽입과 삭제 시에 속도와 성능 면에서 유용하다.

 

 

-Ref

https://www.codingninjas.com/studio/library/difference-between-queue-and-deque-in-c

Difference between Queue and Deque in C++ - Coding Ninjas

https://cplusplus.com/reference/deque/deque/

https://cplusplus.com/reference/deque/deque/

 

 

 

---

- 문제

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

 

- 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

 

- 출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

 

- 예제

//INPUT//
5
3 2 1 -3 -1

//OUTPUT//
1 4 5 3 2

 

 

 

---

 

 

- 구상

같은 단계에 있는, 그리고 이전 포스트에서 시행한 11866번과 유사한 방식으로 풀면 좋겠다고 생각했다.

 

➡ 인덱스 값을 움직이는 것이 아닌, 기준선을 기점으로 숫자들이 움직인다고 생각하자. 마치 기차타고 갈 때, 멈춰있는 나무들이 움직이듯 보이는 것처럼.

그림으로 표현하면 위와 같다. 입력받은 값이 양수이면 왼쪽으로, 음수이면 오른쪽으로 움직이는 듯한 모형을 만들어줄 것이다.

 

➡ 그럼 이전 포스트에서 푼 것과 사실상 동일한 형태가 된다. deque의 push_front(), push_back()의 성질을 잘 이용해 구현하면 된다.

 

➡ 문제가 생기는 부분은 바로 지금부터다. 계속해서 판을 움직이는데, index값을 어떻게 고정시켜서, 즉 터뜨린 풍선의 위치가 원래 어디였는지 어떻게 아냐는 것이다.

 

➡ 처음 풀 때는 vector를 이용해, 입력받은 값을 같이 입력받고, 터진 풍선의 위치를 출력하는 방식을 사용하려 했다. 하지만 움직임을 입력받는 value가 같을 때를 처리하지 못하는 문제가 발생했다.

 

➡ 그래서 class 내지는 struct를 사용하기로 했다. 

 

➡ struct를 사용해, 두개의 int type 객체를 받고, 각각의 객체에는 움직임을 나타내는 변수와 인덱스 값을 받을 것이다.

 

 

 

---

 

 

- 구현

이번에 처음으로, 생성자도, 함수도 없는 struct를 사용했는데, 입력받는 방식과 꺼내오는 방식이 특이했다. 잘 기억해두자.

#include <iostream>
#include <deque>
#define endl '\n'
using namespace std;

struct info {
	int index, num;
};

int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL), cin.tie(NULL);
	
	deque<info> dq;
	int N, num, move;
	cin >> N;

	for (int i = 0; i < N;i++) {
		cin >> num;
		dq.push_front({ i+1,num });   //순서대로 index, num에 들어가진다.
		vec.push_back(num);
	}

	move = dq.back().num;
	dq.pop_back();
	cout << 1 << " ";

	while (!dq.empty()) {
		if (move > 0) {
			for (int i = 0; i < move-1; i++) {
				dq.push_front(dq.back());  //값이 당연하게도 통째로 넘어가서 수고를 덜어준다.
				dq.pop_back();
			}
			cout << dq.back().index << " ";
			move = dq.back().num;    //dq.back()중에서도 무엇을 넘겨줄 것인지 정하게 .num 등으로 표기한다.
			dq.pop_back();
		}
		else {
			for (int i = 0; i < abs(move)-1; i++) {
				dq.push_back(dq.front());
				dq.pop_front();
			}
			cout << dq.front().index << " ";
			move = dq.front().num;
			dq.pop_front();
		}
	}

	
	return 0;

}