프로그래머스 - 풍선 터트리기 문제 (자바)

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

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

풍선이 끝까지 살아남기 위해서는 해당 풍선을 기준으로 오른쪽과 왼쪽에서 가장 작은 값 둘 중 하나보다 작아야 합니다.

왼쪽에서 작은 값만 살려서 오고 오른쪽에서 작은 값만 살려서 온 뒤

현재 풍선이 둘다 보다 작으면 더큰것을 살릴수 있는 기회를 사용하지않고 남길수 있고.

둘중 하나보다만 크다면 기회를 사용하여 남길수있습니다.

그러나 둘다보다 크다면 기회가 한번이기 때문에 불가능합니다.

 

주의점

매번 오른쪽과 왼쪽을 계산하니까 시간초과가 발생하여 DP를 통해서 해결하였습니다.

class BreakBalloon {
    public int solution(int[] a) {
        int answer = 0;
        int[] l_dp = new int[a.length];
        int[] r_dp = new int[a.length];

        l_dp[0] = Integer.MAX_VALUE;
        l_dp[1] = a[0];
        for(int i = 2; i < a.length; i++) {
            l_dp[i] = Math.min(l_dp[i-1], a[i-1]);
        }

        r_dp[a.length - 1] = Integer.MAX_VALUE;
        r_dp[a.length - 2] = a[a.length - 1];
        for(int i = a.length - 3; i >= 0; i--) {
            r_dp[i] = Math.min(r_dp[i+1], a[i+1]);
        }

        for(int i = 0; i < a.length; i++) {
            if(a[i] < l_dp[i] || a[i] < r_dp[i]) {
                answer++;
            }
        }
        return answer;
    }
}