프로그래머스 - 풍선 터트리기(Java)

단순 구현 문제입니다.

dfs로 문제를 해결하기에는 n의 범위가 1,000,000이기 때문에 불가능합니다.

하나의 아이디어가 필요합니다.

 

문제의 조건은 크게 두 가지입니다.

1. 인접한 두 풍선 중 기본적으로 큰 풍선을 터트린다.
2. 단 한 번 작은 풍선을 터트릴 수 있다.

1 ~ n개 사이의 특정 위치를 i라 하겠습니다.

이 i를 살릴 수 있는 방법을 구해야 합니다.

문제에 의해 기본적으로 큰 것을 터트려야 합니다.

그렇다면 좌측과 우측 양쪽 끝에서 부터 시작하여 최소를 저장해 비교하면 어떨까요?

다시말해, 좌측에서 i번째 까지 최소를 구하고 우측에서 i번째까지 최소를 구해서 비교하는 것입니다.

즉, 현재 위치, 좌측 최소, 우측 최소 세 가지를 한 번에 비교하는 것입니다.

단 한번만 작은 풍선을 터트릴 수 있으니 좌측 최소와 우측 최소 중 하나만 터트릴 수 있을테니,

i번째 위치가 좌측 최소, 우측 최소와 비교하여 i가 더 크면 터질 수 밖에 없는 것입니다.

 

이런 방법으로 살아남지 못하는 개수를 구하여 전체 길이에서 빼면 

결국 살아남을 수 있는 것의 개수를 알 수 있습니다.

 

[구현 코드]

class Solution {
    private static int[] leftMinimum, rightMinimum;

    public static int solution(int[] a) {
        int answer = 0;

        int n = a.length;
        int minimum;

        leftMinimum = new int[n];
        rightMinimum = new int[n];

        minimum = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            minimum = Math.min(minimum, a[i]);
            leftMinimum[i] = minimum;
        }

        minimum = Integer.MAX_VALUE;
        for (int i = n-1; i >=0; i--) {
            minimum = Math.min(minimum, a[i]);
            rightMinimum[i] = minimum;
        }

        int notAlive = 0;
        for(int i=0; i<n; i++){
            if(a[i] > leftMinimum[i] && a[i] > rightMinimum[i]){
                notAlive++;
            }
        }

        answer = a.length - notAlive;

        return answer;
    }
}