[Programmers] 풍선 터트리기 - Java

문제

프로그래머스

 

풀이

인접한 두 풍선을 터트릴 수 있는데, 남길 수 있는 풍선의 수를 구하는 문제이다.

 

이 문제의 키포인트는 인접한 풍선중에 작은 풍선을 한번만 터트린다는 것이다.

 

터지는 풍선의 조건을 어떻게 될까?

어떤 임의의 위치에서 풍선에서 왼쪽, 오른쪽의 최솟값보다 크다는 것은 터지는 풍선이라는 의미이다.

 

만약에 왼쪽 오른쪽 끝에서부터 번갈아가면서 큰 풍선들을 터트렸다고 치자.

그러면 제일 왼쪽, 오른쪽에서 제일 작은 풍선 두개가 남을 것이다. 그러면 나머지 풍선들은 다 터졌다.

 

결국 현재 위치를 기준으로 왼쪽, 오른쪽 최솟값보다 크다는 것은 터지는 풍선이다. 나머지는 남길 수 있는 풍선이라는 의미이다.

 

그리고 왜 answer=2부터 시작을 하는가?에 대해서 의문점을 가질 수 있다.

만약에 왼쪽 끝에 있는 풍선이라면, 나머지를 모두 터트렸다고 해도 작은 풍선도 한번은 터트릴 수 있기 때문에, 무조건 양 옆에 풍선은 남길 수 있다.

 

1. 오른쪽 왼쪽에 대한 최솟값의 변수를 선언하고 최솟값을 담을 배열을 선언한다.

 

2. 현재 위치에서 오른쪽, 왼쪽 최솟값을 갱신하고 위치에 최솟값을 담는다.

 

3. 현재 위치에서 오른쪽, 왼쪽 최솟값보다 크다는 의미는 터트려지는 풍선이라는 의미이므로 나머지를 센다.

 

소스코드

class Solution {
    public int solution(int[] a) {
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        
        int length = a.length;
        
        if (length == 1) {
            return 1;
        }
        
        int[] left = new int[length];
        int[] right = new int[length];
        
        for (int i = 0; i < length; i++) {
            if (leftMin > a[i]) {
                leftMin = a[i];
            }
            
            left[i] = leftMin;
        }
        
        for (int i = length - 1; i >= 0; i--) {
            if (rightMin > a[i]) {
                rightMin = a[i];
            }
            
            right[i] = rightMin;
        }
        
        int answer = 2;
        
        for (int i = 1; i < length - 1; i++) {
            if (left[i] < a[i] && right[i] < a[i]) {
                continue; 
            }
            
            answer++;
        }
        
        return answer;
    }
}

 

실행결과