프로그래머스 문제 - 풍선 터트리기

프로그래머스 풍선 터트리기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

일렬로 나열된 풍선들이 주어지며 풍선에는 서로 다른 숫자가 적혀있습니다.
임의의 인접한 두 풍선을 고른 뒤 한가지의 풍선을 터칠 수 있으며, 터진 풍선들 사이의 빈 공간들이 없도록 밀착시켜줍니다.
풍선을 터칠 때는 두 풍선 중 번호가 큰 풍선을 터쳐야하며 작은 숫자를 터트리는 행위는 단 한번만 가능합니다.
1개까지 풍선을 남기는 것이 가능한 풍선들의 갯수를 출력하세요.

문제 풀이

인접한 풍선을 터칠 때는 무조건 큰 수만 터뜨릴 수 있으므로 제일 작은 수가 남을 수 있게 된다.
하지만 단 한번 작은 숫자를 터트릴 수 있으므로 터트리는 순서에 따라 남는 풍선이 달라질 수 있게 된다.

예를 들어 한 풍선을 기준으로 양 옆의 풍선들을 기준에 맞춰 터트려나가면 결국 왼쪽 오른쪽의 가장 작을 수들이 남게 된다.
양쪽이 한 풍선보다 작을 경우 풍선을 남기지 못하겟지만 한 쪽만 풍선이 작을 경우 풍선을 남길 수 있게 됩니다.
3 9 5로 나열된 풍선들은 9 풍선은 남기지 못하겟지만 3 9 11로 나열된 풍선들은 9 풍선을 남길 수 있게 됩니다.

그러므로 한 기준점에서 왼쪽 오른쪽 방향의 수들 중 최솟값을 알고 있으면 기준점의 풍선이 남길 수 있을지 알 수 있게 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    int left[1000000] = {0,};
    int right[1000000] = {0,};
    left[0] = 1000000001;
    right[a.size()-1] = 1000000001;

    //왼쪽과 오른쪽에서부터 제일 작은 숫자를 찾아 배열에 입력
    for(int i = 1; i < a.size(); i++)
    {
        if(left[i-1] > a[i-1])
        {
            left[i] = a[i-1];
        }
        else
        {
            left[i] = left[i-1];
        }
        
        if(right[a.size()-i] > a[a.size()-i])
        {
            right[a.size()-1-i] = a[a.size()-i];
        }
        else
        {
            right[a.size()-1-i] = right[a.size()-i];
        }
    }
    //비교할 풍선보다 작은수가 더 클 경우 남기는 것이 가능
    for(int i = 0; i < a.size(); i++)
    {
        if(left[i] > a[i] || right[i] > a[i])
        {
            answer++;
        }
    }
    
    return answer;
}

출처

https://school.programmers.co.kr/learn/courses/30/lessons/68646