< 백준 BaekJoon : 2346번 풍선 터뜨리기> C++

<< 문제 >>

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

2346번: 풍선 터뜨리기

 

풍선을 터뜨린 후 나온 쪽지에 적힌 수 만큼 이동해서 또 터뜨리는 문제 

 

이 문제는 deque(deck)을 이용해 해결하면 된다. 

 

`

text 3 2 1 -3 -1

초기 : 1 2 3 4 5
1차 : 4 5 2 3 다음에 4를 터뜨림
2차 : 2 3 5  다음에 5를 터뜨림
3차 : 2 3 다음에 3을 터뜨림
4차 : 2

 

이런 형태로 뒤로 돌리고 앞으로 다시 돌리고 하면서 문제를 해결할 수 있다. 

 

<< 코드 >>

 

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

void teskDq(int *textList, deque<int> &dq) {
  int target = 1;
  dq.pop_front();
  cout << target << ' ';
  
  int text;
  while(!dq.empty()){
    text = textList[target];
    if(text > 0){
      for(int i=1; i < text; i++){
        dq.push_back(dq.front());
        dq.pop_front();
      }
      target = dq.front();
      dq.pop_front();
    }
    else{
      text *= -1;
      for(int i=1; i < text; i++){
        dq.push_front(dq.back());
        dq.pop_back();
      }
      target = dq.back();
      dq.pop_back();
    }
    cout << target << ' ';
  }
  
}

int main() {
  deque<int> dq;
  
  int num;
  cin >> num;
  int *textList = new int[num+1];

  for (int i = 1; i <= num; i++) {
    int text;
    cin >> text;
    textList[i] = text;

    dq.push_back(i);
  }
  teskDq(textList, dq);
  delete[] textList;
}

 

 

 

<< GitHub>> 

https://github.com/J2on/StudyAlgorithm_Part2/tree/81e6cabe343e50e8f74a11755b4257f424de4350/%EB%B0%B1%EC%A4%80/Silver/2346.%E2%80%85%ED%92%8D%EC%84%A0%E2%80%85%ED%84%B0%EB%9C%A8%EB%A6%AC%EA%B8%B0