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

풍선 터트리기 링크

다들 해설을 보러 오셨을거라 생각하고 진행하겠습니다.

문제의 핵심

이 문제의 핵심은 인접한 풍선 중 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 가능하다는 것

또한 여기서 해결해야 되는 문제는? 어떤 풍선이 마지막으로 남을 수 있을까라는 것임.

1. 가장 작은 수를 가진 풍선은 남을 수 있음. 큰 풍선을 다 터트리면 결국 제일 작은 수 풍선 하나만 남을테니깐
2. 두 번째 작은 수 또한 터트릴 수 있음. 번호가 더 작은 풍선을 터트리는 행위를 1번 할 수 있기 때문에

그럼 특정 수가 남을 수 있는 경우는 무엇인가?

결국 특정한 수가 남는 경우는 그 수 기준으로 좌우에 모든 풍선이 터지는 경우가 될 것입니다.

그럼 마지막에 남는 수 3개를 예시로 들어보겠습니다.

A, B, C 라는 풍선이 연달아 남았습니다.

우리는 B가 최종으로 남을 수 있는 풍선인가에 대해서 궁금합니다.

B가 최종으로 남을수 있는 경우의 수는?

A, C 둘 중의 수가 하나라도 B보다 커야합니다.

문제에서 주어진 예시를 보죠.

총 9개의 숫자가 주어집니다..
각 숫자 기준으로 좌우에 모든 풍선이 터져서 올 수 있는 수를 구한것이 3번째 행입니다.

자 그럼 저 값을 보면 특정 인덱스에 해당하는 풍선이 살아남을 수 있는지 없는지 알 수 있습니다.
결국 좌우에 큰 값을 터트리게 되면 특정 인덱스 기준으로 가장 작은 값들만 살아남기 때문이죠.
따라서 이 경우 0번 풍선, 5, 6, 7, 8, 9 풍선만 살아남게 되어서 6을 반환하게 됩니다.

public class 프로그래머스_풍선터트리기 {
    public int solution(int[] a) {

        int[] leftMin = new int[a.length];
        int[] rightMin = new int[a.length];

        Arrays.fill(leftMin, Integer.MAX_VALUE);
        Arrays.fill(rightMin, Integer.MAX_VALUE);

        for (int i = 1; i < a.length; i++) {
            int j = a.length - i - 1;
            leftMin[i] = Math.min(leftMin[i - 1], a[i - 1]);
            rightMin[j] = Math.min(rightMin[j + 1], a[j + 1]);
        }

        int answer = 0;

        for (int i = 0; i < a.length; i++) {
            if (leftMin[i] > a[i] || rightMin[i] > a[i])
                answer++;
        }

        return answer;
    }

   
}