[Lv.3] 풍선 터트리기

맨 앞,뒤는 해당 풍선을 제외하고 남은 풍선을 모두 큰 풍선만 골라 터트린다면 남은 풍선과 맨 앞(뒤)풍선 중 어떤게 크든 작든 아직 작은 풍선을 터트리는 기회가 남아 있기에 무조건 남길 수 있다.

 

여기서, 더 나아가면 3개의 풍선이 있다고 했을 때, 가운데 풍선이 양 옆의 풍선보다 크다면 절대 풍선을 남길 수 없다 ( 수가 더 작은 풍선을 터트리는 기회는 최대 1회 이므로)

 

여기서 잘 생각해보면 i번째 풍선을 남기기 위해선

0~i-1번째 풍선을 모두 수가 큰 풍선만 터트려 1개를 남기고

i+1~n번째 풍선을 마찬가지로 큰 풍선만 터트려 1개를 남긴 후

이 3개의 풍선을 비교하여 i가 제일 크다면 i번째 풍선을 절대 남길 수 없게된다.

 

이제 푸는 방법을 알았으니 코드로 구현해보면

배열을 0번부터 끝까지 순회하면서 0~i까지의 값 중 최소의 값을 minLeft[i+1]에 저장한다.

즉, minLeft[i+1]은 i+1번째 수의 왼쪽 값들 중 최소를 의미한다.

 

반대로 배열의 끝부터 0번까지 순회하며 최소값을 minRight[i+1]에 저장한다.

마찬가지로 minRight은 오른쪽의 수 중 최소를 의미한다.

 

이제 다시 배열의 처음부터 순회를 하며 해당 원소의 값이 minLeft,minRight보다 큰 경우를 찾아( 남을 수 없는 풍선을 찾아) 정답에서 차감한다.

이렇게 되면 남을 수 없는 풍선을 모두 없앴기에 answer의 값이 남길 수 있는 풍선의 수가 된다.

 

코드

import java.util.Arrays;

class Solution {
    public int solution(int[] a) {
        int answer = a.length;
        //맨 앞, 맨 뒤는 항상 남길 수 있다
        //가운데수가 양 옆의 수보다 크다면 그 수는 추가할 수 없다.
        //I번째수가 가능하려면 0~i-1까지 최솟값, i+1~n까지 최솟값과 비교한다..!
        int[] minLeft=new int[a.length+1];
        int[] minRight=new int[a.length+1];
        int nowMin=Integer.MAX_VALUE;
        minLeft[0]=Integer.MAX_VALUE;
        for (int i = 0; i < a.length-1; i++) {
            nowMin=Math.min(nowMin,a[i]);
            minLeft[i+1]=nowMin;
        }

        nowMin=Integer.MAX_VALUE;
        minRight[a.length-1]=Integer.MAX_VALUE;
        for (int i = a.length-1; i >0; i--) {
            nowMin=Math.min(nowMin,a[i]);
            minRight[i-1]=nowMin;
        }

        for (int i = 0; i < a.length; i++) {
            if(a[i]>minLeft[i]&&a[i]>minRight[i])
                answer--;
        }

        return answer;
    }
}