[알고리즘] 풍선 터트리기 (월간 코드 챌린지 시즌1 - 9월)

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

 월간 코드 챌린지 9월에 나온 레벨3 문제다. 9월 10월 둘 다 풀면서 느낀건 브루트 포스 문제보단 아이디어로 시간복잡도를 최소화 해가면서 푸는 방식을 원하는 것 같다.

 이 문제 또한 N이 최대 1백만이기에 O(N ^ 2)으론 풀 수가 없다.

 

Solution

 먼저 파악해야할 것은 어떤 특정값이 최후까지 살아남는지 알아볼 때, 양쪽에 있는 수들은 서로 만날 수가 없다. 그렇기에 특정값을 기준으로 왼쪽 오른쪽으로 나누어서 살펴봐야 한다.

 그리고 양쪽에서 최후까지 살아남을 수 있는 수는 각각 2가지가 되는데 '최소값, 최소값보다 한단계 더 큰 값'이 될 수 있다.

 최소값은 무조건 큰 수만 제거한다고 쳤을 때 나오는 수고, 최소값보다 한단계 더 큰 값은 1번 작은 수를 제거했을 때 나올 수 있는 수다. 

 

 여기서 하나의 결론을 도출할 수 있는데 만약 양쪽의 최소값 중 하나라도 기준값보다 크다면 그 기준값은 최후까지 살아남을 수 있다. 양쪽의 최소값이 나올 때까지는 작은 수를 한 번도 터뜨리지 않았고 기준값보다 최후까지 남은 최소값들 중 기준값보다 작은 값이 하나 존재한다 하더라도 1번 작은 수를 터뜨릴 수 있기 때문에 큰 값이 하나만이라도 있으면 무조건 살아남을 수 있다.

 

 그렇기에 0~n - 1까지의 각각 요소까지의 최소값들을 저장하는 배열, n - 1 ~ 0까지의 요소들의 최소값들을 저장하는 배열을 만든 뒤 조건 검사를 하면 3N만에 풀 수 있다.

 

class Solution {

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

        boolean[] isCould = new boolean[a.length];
        isCould[0] = true;
        isCould[isCould.length - 1] = true;

        int[] left_min = new int[a.length];
        int[] right_min = new int[a.length];

        //왼쪽에서 부터 min 값
        left_min[0] = a[0];

        for(int i = 1;i < a.length;i++)
            left_min[i] = Math.min(left_min[i - 1], a[i]);

        //오른쪽에서부터 min 값
        right_min[a.length - 1] = a[a.length - 1];

        for(int i = a.length - 2;i >= 0;i--)
            right_min[i] = Math.min(right_min[i + 1], a[i]);

        /*
    MIN - MIN : 하나만 a[i]보다 크면 됨
     */
        for(int i = 1;i < a.length - 1;i++ )
        {
            if(left_min[i - 1] > a[i] || right_min[i + 1] > a[i])
            {
                isCould[i] = true;
                answer++;
            }
        }


        return answer;
    }
}