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

문제

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

코딩테스트 연습 - 풍선 터트리기

---

풍선 값들이 주어지고 인접한 풍선 2개를 골라서 터트리면서 남을 수 있는 마지막 한 개의 풍선의 개수를 찾는 문제입니다. 조건으로 두 가지가 있는데, 일단 두 풍선에서 무조건 큰 값을 가진 풍선을 터트릴 수 있습니다. 거기에 또 다른 조건은 전체 배열에서 인접한 풍선 2개를 선택했을 때 딱 한 번만 작은 값을 가진 풍선을 터트릴 수 있습니다.

주어진 예시에서 가능한 경우의 수들을 먼저 찾는게 우선인 것 같습니다. 최종으로 남을 수 있는 풍선의 경우의 수를 찾는 것이니 가능한 경우가 존재하면 개수를 세어주면 됩니다.  만약 풍선 값이 최소라면 그냥 막 터트려도 자기 자신이 남을 수 있을 겁니다.

여기서 풍선의 위치도 중요합니다. 만약 풍선의 값이 최대값인데 오른쪽 끝에 있다면 전에 있는 모든 풍선들을 비교하면서 큰 수 우선으로 지우고 가장 작은 값이 남았을 때 작은 값을 터트리는 기회를 사용한다면 최종적으로 남을 수 있을 겁니다.

하지만 중간에 끼어 있다면 어떻게 하든 최대값은 터트릴 수 없습니다. 따라서 선택한 값의 양 옆으로 최소값들을 비교해서 그 최솟값이 자신보다 큰 게 있다면 작은 값을 터트리는 기회를 한번 쓸 수 있으니까 살아남을 수 있을 겁니다.

---

소스코드 

#include<bits/stdc++.h>

using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    vector<int> left(a.size());
    vector<int> right(a.size());
    
    int MIN =a[0];
    for(int i=0; i<a.size(); i++){
        if(MIN > a[i]) MIN =a[i];
        left[i]= MIN;
    }
    
    MIN = a[a.size()-1];
    for(int i=a.size()-1; i>=0 ; i--){
        if(MIN > a[i]) MIN= a[i];
        right[i] = MIN;
    }
    
    for(int i=0 ; i<a.size(); i++){
        if(a[i] <=left[i] || a[i] <=right[i]) answer++;
    }
    
    return answer;
}