프로그래머스 [Lv. 3] 풍선 터트리기 {언어 : Java} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/68646?language=java

프로그래머스

정답 코드

class Solution {
    public int solution(int[] a) {
        int lenA = a.length;
        if (lenA <= 2) return lenA;
        
        int last = lenA - 1;
        int[] leftMin = new int[lenA];
        int[] rightMin = new int[lenA];
        
        // 왼쪽에서 최소값 채우기
        leftMin[0] = a[0];
        for (int i = 1; i < lenA; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], a[i]);
        }
        
        // 오른쪽에서 최소값 채우기
        rightMin[last] = a[last];
        for (int j = last - 1; j > -1; j--) {
            rightMin[j] = Math.min(rightMin[j + 1], a[j]);
        }
        
        int answer = 2;
        for (int k = 1; k < last; k++) {
            if (a[k] <= leftMin[k] || a[k] <= rightMin[k]) {
                answer++;
            }
        }
        
        return answer;
    }
}

풀이 방법

 

1. 각 풍선이 최후까지 남을 수 있는 조건을 확인하려면, 각 풍선이 왼쪽과 오른쪽에서 접근하는 최소값들보다 작아야 한다.
   1. 다시 말해, 해당 풍선이 자신보다 작은 풍선들 사이에 끼어 있지 않아야 한다.
2. 이를 위해, 배열 a의 각 위치에서 왼쪽과 오른쪽의 최소값을 계산한다.
3. leftMin 배열은 각 위치에서 그 위치까지의 최소값을 저장하고, rightMin 배열은 각 위치에서 그 위치 이후의 최소값을 저장한.

예시

배열 a = [-16, 27, 65, -2, 58, -92, -71, -68, -61, -33] 가 주어졌을 때

 

1. eftMin 배열 계산:

leftMin[0] = a[0] = -16
leftMin[1] = min(leftMin[0], a[1]) = min(-16, 27) = -16
leftMin[2] = min(leftMin[1], a[2]) = min(-16, 65) = -16
leftMin[3] = min(leftMin[2], a[3]) = min(-16, -2) = -16
leftMin[4] = min(leftMin[3], a[4]) = min(-16, 58) = -16
leftMin[5] = min(leftMin[4], a[5]) = min(-16, -92) = -92
leftMin[6] = min(leftMin[5], a[6]) = min(-92, -71) = -92
leftMin[7] = min(leftMin[6], a[7]) = min(-92, -68) = -92
leftMin[8] = min(leftMin[7], a[8]) = min(-92, -61) = -92
leftMin[9] = min(leftMin[8], a[9]) = min(-92, -33) = -92

leftMin = [-16, -16, -16, -16, -16, -92, -92, -92, -92, -92]

 

 

2. rightMin 배열 계산:

rightMin[9] = a[9] = -33
rightMin[8] = min(rightMin[9], a[8]) = min(-33, -61) = -61
rightMin[7] = min(rightMin[8], a[7]) = min(-61, -68) = -68
rightMin[6] = min(rightMin[7], a[6]) = min(-68, -71) = -71
rightMin[5] = min(rightMin[6], a[5]) = min(-71, -92) = -92
rightMin[4] = min(rightMin[5], a[4]) = min(-92, 58) = -92
rightMin[3] = min(rightMin[4], a[3]) = min(-92, -2) = -92
rightMin[2] = min(rightMin[3], a[2]) = min(-92, 65) = -92
rightMin[1] = min(rightMin[2], a[1]) = min(-92, 27) = -92
rightMin[0] = min(rightMin[1], a[0]) = min(-92, -16) = -92

rightMin = [-92, -92, -92, -92, -92, -92, -71, -68, -61, -33]

 

3. 풍선이 최후까지 남을 수 있는지 확인:

각 풍선의 번호 a[i]가 leftMin[i]보다 작거나 같거나, rightMin[i]보다 작거나 같으면 그 풍선은 최후까지 남을 수 있다.

느낀점

• 큰 풍선들을 터트리면서 오기 때문에 작은 풍선들만 남느다는 것을 놓쳤다.
• 생각보다 어려웠고 두 번 틀리고도 문제를 찾지 못했으며 dp값을 치환하는 방식에서 이미 틀렸다.