[C/C++] 백준 #2346 풍선 터뜨리기(데크 자료구조)

#2346 풍선 터뜨리기 문제는 자료구조를 사용하면 좋습니다.  제 경우에는 데크 자료구조를 이용하여 문제를 풀었습니다.

 

문제의 링크입니다.

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

2346번: 풍선 터뜨리기

 

데크 자료구조는, 큐와 스택 모두 사용하여도 성능이 좋습니다.  그래서 큐 대신에 많이 사용되는 편입니다.

 

구현은 데크를 이용하여 적절한 삭제만 해주시면 됩니다.  데크 자체가 앞과 뒤 연산에는 효율적이지만, 중간에 데이터를 넣는 작업이나 빼는 작업의 경우에는 데이터 개수가 N 일 때, \(O(N)\)의 시간복잡도를 보입니다.

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #2346 - Baloon
//        - by Aubrey Choi
//        - created at 2020-01-13
//----------------------------------------------------------
#include <stdio.h>
#include <deque>

struct Elem { Elem(int i, int s):idx(i),v(s){} int idx, v; };
int main()
{
    std::deque<Elem> deq;
    int n, s, i;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&s),deq.push_back(Elem(i+1,s));
    for(i=0;n;) 
    { 
        Elem &t=deq[i]; s=t.v;
        printf("%d ",t.idx);
        deq.erase(deq.begin()+i);
        if(!--n) i=0; else if(s<0) i=(i+n*1000+s)%n; else i=(i+s-1)%n; 
    }
    putchar('\n');
}

popping balloon