[개쉬운 풀이] 백준 2346 풍선 터뜨리기

 

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

 

생각

왼쪽 오른쪽으로 이동하는 것을 deque를 이용하여 값들을 이동시켜 pop_front를 통해 값을 가져오고 제거하기로 했다.

deque의 pop()은 O(1) 이기 때문에 원하는 값 만큼 풍선을 옮겨도 시간복잡도가 O(n)이기 때문에 시간초과는 발생하지 않을 것 같다.

풀이

1. deque를 pair로 생성하여 <'풍선 안의 쪽지 값' , '풍선 번호'> 로 만들어 주었다.
2. 이후 풍선 안의 값이 + 인지 - 인지 확인하여 isPlus와 isMinus로 나누어주었다.
3. isMinus는 맨 뒤값을 앞으로 가져오는 방식으로 인덱스를 조절하였다.
4. isPlus는 앞값을 뒤로 보내는 방식으로 인덱스를 조절하였다.
5. 이후 target 풍선을 제거해준다
6. ** 이때 다음 풍선값 : nextNumber는 음수가 나올 수 있으므로 각 포문에서 abs()함수를 통해 절대값으로 만들어 주었다.
7. while문은 풍선이 모두 터질때까지 돌려주었다.
8. answer 에 담아서 출력 형태에 맞게 출력한다.

 

코드

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

int n;
vector<int> answer;
deque<pair<int,int>> dq;

void input(){
    cin >> n;

    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        dq.push_back(make_pair(tmp, i+1));
    }
}

# 풍선의 값이 양수인 경우
int isPlus(int nextNumber){
    for(int i = 0; i < abs(nextNumber)-1; i++){
        pair<int,int> tmp = dq.front();
        dq.push_back(tmp);
        dq.pop_front();
    }
    pair<int,int> target = dq.front();
    answer.push_back(target.second);
    dq.pop_front();

    return target.first;
}

# 풍선의 값이 음수인 경우
int isMinus(int nextNumber){
    for(int i = 0; i < abs(nextNumber); i++){
        pair<int,int> tmp = dq.back();
        dq.push_front(tmp);
        dq.pop_back();
    }
    pair<int,int> target = dq.front();
    answer.push_back(target.second);
    dq.pop_front();

    return target.first;
}

void print(){
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
}

void sol(){
    //첫번째는 무조건 맨 앞을 터뜨린다.
    int nextNumber = 1;

    while(!dq.empty()){
       if (nextNumber > 0) nextNumber = isPlus(nextNumber);
       else nextNumber = isMinus(nextNumber);
    }
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    input();
    sol();
    print();
    return 0;
}