[BOJ/C++]2346번_풍선 터뜨리기

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

 

##문제 풀기 전 내가 알고 있었어야 할 개념:

1_Stack,Queue,Deque 객체에 2개 이상 자료형 형태로 선언, 사용하기

   1_1) 선언 방법  : pair

 자료형태(스택,덱,큐) <pair<자료형타입1,자료형 타입2...,자료형타입n>> 객체 이름

=> ex) stack <pair<int , string>> S;

   1_2) 객체에 원소 대입(저장) : make_pair(n1,n2,...,n);

=> ex) Q.push(make_pair(3,"하이하이")); // Q의 Rear에 (3,"하이하이")라는 pair의 값을 추가 삽입하기

    1_3) 원소 호출 방법 : 원소.frist() / 원소.second ... 등 

=> ex) int data = Q.front.first(); //  Queue 객체의 Q의 front()의 원소 중 첫번째 타입의 원소 추출해서, data변수에 저장

2_ ★이 문제의 자료형 객체를 Queue가 아닌 Deque를 선택한 이유 :

[핵심]

• Queue : 원형 탁자의 N개의 원소를 오른쪽 이동 연산만 필요할 때, 사용 (ex : 요세푸스 문제)
• Deque : 원형 타자의 N개의 원소를 왼쪽/오른쪽 이동 연산 둘다 필요할 때, 사용 (ex : 해당 문제)

[자세한 해설 원리와 핵심]

[해설]

Deque와 원형탁자 원리 노트정리.pdf

1.10MB

[해당 문제를 풀기위한 핵심 개념]

3_ ▲while() 내의 Pop(),front() .. 등 반복시행 시, "종료 시점"  :

=> 비어(empty)있을 시점으로 해야한다.,  (front(), Pop().. 등등의 연산이 되지 않도록 햐여헌더,) 

 

#include <iostream>
#include <deque>
 
using namespace std;
 
deque<pair<int, int>> DQ;
 
int main() {
 
    int N;
 
    //풍선 개수 입력
    cin >> N;
 
    //풍선 안에 종이값 입력 저장
    for (int i = 0; i < N; i++) {
        int input;
        cin >> input;
        DQ.push_back(make_pair(i + 1, input));
        //★Deque이므로, back에 push 해야 입력된 순서대로 저장된다.
        //first(순서번호) :    1(f) 2 3 4  5(r)
        //second :            3(f) 2 1 -3 -1(r)
    }
 
    //N번 연산시작
    while (1) {
        //원형 탁자의 첫번째 풍선의 종이값 확인
 
        int data = DQ.front().second;
        //종이값 확인후, 순번출 력 => Pop();
        cout << DQ.front().first << ' ';
        
        DQ.pop_front();
 
        if (DQ.empty()) return 0; //▲마지막 번째 출력,Pop 후, 비어있다면 => 종료
        
        if (data > 0) {//오른쪽 이동 => data - 1 번 만큼 연산
            for (int i = 0; i < data - 1; i++) {
                DQ.push_back(DQ.front());
                DQ.pop_front();
            }
        }
        else if (data < 0) {//왼쪽 이동 => data번 만큼 연산
            data *= -1;
            for (int i = 0; i < data; i++) {
                DQ.push_front(DQ.back());
                DQ.pop_back();
            }
        }
 
        //왼쪽, 오른쪽 연산 이동 후, 다음 풍선을 front()로 지정되도록 했다
        //★해설과 핵심개념 참조
 
    }
 
    return 0;
}