[BOJ 2346] 풍선 터뜨리기

문제 : 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.
우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.
예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

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

2346번: 풍선 터뜨리기

문제 분석 

• 이 문제는 가장 마지막 인덱스 다음 인덱스가 처음 인덱스라는 점을 잘 생각해야 한다.
• 배열 기반으로 문제를 풀어 이 부분을 예외처리를 해주려 했다.
• 종이의 적혀 있는 값의 절댓값은 N보다 작으므로 Mod 연산을 해주지 않아도 풀 수 있을 것 같다.

vector<int>balloon;
int main(){
    int n;
    cin>>n;
    balloon.push_back(0);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        balloon.push_back(x);
    }// 1번
    int k=1;
    for(int i=0;i<n;i++){
        int j;
        cout<<k<<" ";//1번부터 i번 출력
        j = k+balloon[k];//j는 i번에 i번에 있는값 더한거
        if(j<=0)j=n+j;
        else if(j>=n) j=j-n;
        while(balloon[j]==0){
            if(balloon[k]<0){
                j--;
                if(j==0)j=n;
            }
            else {
                j++;
                if(j==n+1)j=1;
            }
        }
        balloon[k] = 0;
        k=j;
    }
    return 0;
}

위 사진과 같은 논리로 이 코드를 제출했더니 "틀렸습니다"가 떴다....
아직도 어떤 부분을 놓친건지 잘 모르겠지만 암튼 틀렸다. (다시 생각해보고 생각나면 어떤 부분이 틀렸는지 적어 놓겠다.)
위 논리에서 틀린 부분을 찾지 못해 아예 다른방식으로 풀어 보려했고, queue라이브러리의 <deque>라는 stl을 알게 됐다.

deque<pair<int,int>>balloons;
int n;
void cycle(pair<int,int>x){
    pair<int,int> next;
    cout << x.first<< " ";
    int v = x.second;
    if(balloons.empty()) return;
    if(v > 0){
        v-=1;
        while (v--){
            balloons.push_back(balloons.front());
            balloons.pop_front();
        }
        next = balloons.front();
        balloons.pop_front();
        cycle(next);
    }
    else{
        v=-v;
        v-=1;
        while(v--){
            balloons.push_front(balloons.back());
            balloons.pop_back();
        }
        next = balloons.back();
        balloons.pop_back();
        cycle(next);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        balloons.push_back({i,x});
    }
    int firstV = balloons.front().second;
    balloons.pop_front();
    cycle({1,firstV});
    return 0;
}

<deque>는 앞,뒤에서 둘다 삽입,  삭제가 가능한 queue라 생각하면 이해가 쉽다. 맨 뒤, 혹은 앞에 요소를 삽입할수도 있고, 맨 뒤랑 앞에 있는 요소를 참조, 삭제할 수도 있다.

deque를 이용하여 문제를 다시 풀었다. 먼저 풍선의 위치에 대한 번호와 풍선안에 있는 값을 pair로 deque에 저장한다.
그리고 1번 값을 pop하고 1번부터 cycle이라는 함수를 재귀로 실행한다.

cycle은 다음과 같은 기능을 한다.

• 들어온 pair의 첫번째 값(풍선의 위치)을 출력한다. 
• 풍선에 있는 종이가 양수면 맨뒤에 있는 값을 꺼내 맨앞에 넣는다.
• 음수면 맨앞에 있는 값을 꺼내 맨뒤에 넣는다.
• 다음 값을 새로운 값에 복사한다.
• 다음 값을 삭제한다.(풍선을 터뜨린다)
• stl이 비면 재귀를 멈춘다.

위와 같이 풀었더니 "정답입니다"가 떴다.

느낀 점

• 이 문제를 풀며 <deque>라는 stl을 알게됐다. 물론 아직 어색하지만, 존재를 알고 있는것과 존재를 모르고 있는것에는 큰차이가 있을 것이다. deque를 이용하여 문제를 쉽게 풀수 있을 거 같다.
• 처음 vector를 사용한 방식은 사실 이 논리가 틀리지 않음을 확신할 수 없었다. 문제에서 풍선터뜨리는 방식을 좀 바꿔서 문제를 풀려고 했기 때문이다. 이런 애매한 논리로는 문제푸는데에 무리가 있을 수 있다.

시간 복잡도

• 입력 , n번 반복 ->O(n)
• cycle함수(재귀), n번 반복
  풍선에 들어 있는 값 만큼 push, pop(while문), 최악의 경우 n번 반복( |v| ≤ |n| ) ->O(n)
  ➣ O(n^2)