[백준 2346번] 풍선 터뜨리기

🔗알고리즘 문제

기본적인 deque문제이지만 deque에 대해 잘 모르던 시절 풀게 된 문제라 힘들게 해결하였다,, deque라는 자료구조에 대해 더 잘 알수있게 된 문제이다.

문제 분석

이 문제는 1부터 n까지의 풍선을 규칙에 맞게 터트린 후 터트린 순서를 출력하는 문제이다.

규칙은 다음과 같다.

1. 제일 처음에는 1번 풍선을 터뜨린다.
2. 풍선 안에 있는 종이를 꺼내어 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다.
3. 종이의 숫자가 양수일 경우 오른쪽으로 음수일 경우 왼쪽으로 이동한다.
4. 이미 터진 풍선은 지나쳐서 이동한다.

예를 들어 다섯 개의 풍선에 차례대로 3, 2, 1, -3, -1이 적혀 있다면 3이 적힌 1번 풍선, 이동 후 -3이 적혀 있는 4번 풍선 이동 후 -1이 적혀 있는 5번 풍선 ・ ・ ・

이러한 과정을 반복하여 1, 4, 5, 3, 2 순서로 풍선이 터지게 된다.

발상

이 문제에서 가장 주의깊게 생각해야 하는 부분은 풍선들의 인덱스 이동이다. 인덱스 이동을 구현하기 위해서는 주어진 값 만큼 한칸씩 이동하며 그 칸으로 이동이 가능한지 확인하는 작업이 필요하다.

풍선들의 배열을 bool값 배열로 만들어주고 터진 풍선의 인덱스는 true값으로 바꿔주었다.

그리고 칸 이동을 하며 만약 이미 터진 풍선을 발견했다면 단순히 한칸 더 이동하면 되는 문제기때문에 for문을 한번 더 진행하는 방식을 통하여 구현하였다.

알고리즘 설계

1. 기본값이 전부 false인 풍선 수 만큼의 배열을 for문을 돌며 인덱스를 옮기기
   만약 중간에 true값을 발견했다면 한칸 더 옮겨줌
2. 최종 인덱스를 출력 후, 다음 값들로 계속 반복하기

코드

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

bool check[1000] = {true, false};

int FindAIndex(int max, int currentIndex, int value){
    int checkValue = 0;
    for(int i = ((value > 0) ? 1 : -1); ((value > 0) ? i <= value : i >= value); ((value > 0) ? i++ : i--)){
        checkValue = currentIndex + i;

        while(checkValue > max || checkValue <= 0){
            if(checkValue > max)
                checkValue -= max;
            else if(checkValue <= 0)
                checkValue = max - abs(checkValue);
        }

        if(check[checkValue - 1]){
            currentIndex += (value > 0) ? 1 : -1;
            (value > 0) ? --i : ++i;
        }
    }

    check[checkValue - 1] = true;
    return checkValue;
}

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

    int ballonCount;
    int index = 1;

    vector<int> ballonNums;

    cin >> ballonCount;

    for(int i = 0; i < ballonCount; i++){
        int input;
        cin >> input;
        ballonNums.push_back(input);
    }

    for(int i = 0; i < ballonCount; i++){
        cout << index << " ";
        if(i < ballonCount - 1)
            index = FindAIndex(ballonCount, index, ballonNums[index - 1]);
    }
}