[GDSC Week2-3] 백준 2346번:: 풍선 터뜨리기 (C++)

 

 

* 생각한 아이디어 및 문제 풀이

1. 시작과 끝이 이어진 문제라 deque으로 풀어야 겠다고 생각했다.
2. 풍선의 값은 기본적으로 배열에 넣고, deque에는 각각 index를 넣는다. 
3. 풍선 터뜨리고 움직이는 수가 양수라면 먼저 터뜨리고 움직이므로 1을 뺀만큼 이동을 한다.
4. 음수라면 그대로 취한만큼 이동한다.

 

* 코드

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

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    
    deque<int> deq;
    vector<int> result;
    int N, ballonValue[1001];
    cin >> N;
    
    for(int i=0; i<N; i++){
        deq.push_back(i+1);
        cin >> ballonValue[i];
    }
    
    for(int i=0; i<N; i++){
        result.push_back(deq.front());
        int val = ballonValue[deq.front()-1];
        deq.pop_front();
        
        if(val>0){
            for(int j=0; j<(val-1); j++){
                deq.push_back(deq.front());
                deq.pop_front();
            }
        } else{
            for(int j=0;  j<(-val); j++){
                deq.push_front(deq.back());
                deq.pop_back();
            }
        }
    }
    for(auto& i :result) cout<<i<<' ';
}

 

* 회고

값은 배열로, 인덱스는 덱으로, 최종 결과는 vector로 넣는 것이 비효율적이라는 생각이 들어서 다른 코드를 찾아보니 대부분 pair로 푼 것을 알 수 있었다.

나에게 pair은 아직 익숙하지 않아서 이를 이용하는 연습을 많이 해보아야 겠다.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

typedef pair<int, int> pairs;
deque<pairs> balloon_deque;

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

    int n, value;
    cin >> n;
	
    for (int i=0; i<n; i++) {
        cin >> value;
        balloon_deque.emplace_back(i+1, value);
    }

    while (!balloon_deque.empty()) {
        pairs balloon = balloon_deque.front();
        cout << balloon.first << ' ';
        balloon_deque.pop_front();

        // 해당 수 전까지의 다시 push
        // 타겟 풍선은 pop
        for (int i=1 ; i<balloon.second; i++) {
            balloon_deque.push_back(balloon_deque.front());
            balloon_deque.pop_front();
        }
        
        for (int i=0; i>balloon.second; i--) {
            balloon_deque.push_front(balloon_deque.back());
            balloon_deque.pop_back();
        }
    }
}

GDSC NayeonKeum님의 회원님의 코드를 참고하여 풀어보았다. 

 

 

* 문제 링크 : https://www.acmicpc.net/problem/2346

2346번: 풍선 터뜨리기