[프로그래머스] 풍선 터트리기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/68646

문제 풀이

• 완전 탐색은 불가능 하다.
• 문제의 조건에서 알 수 있는 사실은 특정 풍선 좌, 우측으로 해당 수보다 작은 수가 존재하면 해당 풍선은 마지막까지 존재할 수 없는 풍선이다.
• 따라서 풀이는 다음과 같다.

  leftMin[] : 좌측부터 해당 좌표까지 최솟값
  rightMin[] : 우측부터 해당 좌표까지 최솟값
  leftMin[i] < a[i] 이고 rightMin[i] < a[i] 이면 해당 풍선은 카운트X

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int[] leftMin, rightMin;
    public int solution(int[] a) {
        //초기화
        int N = a.length;
        leftMin = new int[N];
        rightMin = new int[N];
        
        //leftMin[] : 좌측부터 해당 셀까지 최소값
        //rightMin[] : 우측부터 해당 셀까지 최소값
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            min = Math.min(min, a[i]);
            leftMin[i] = min;
        }
        min = Integer.MAX_VALUE;
        for (int i = N-1; i >= 0; i--) {
            min = Math.min(min, a[i]);
            rightMin[i] = min;
        }
        
        int result = 0;
        //해당 셀이 살아남을 수 있는지 판별 
        for (int i = 0; i < N; i++) {
            if (leftMin[i] < a[i] && rightMin[i] < a[i]) 
                continue;
            result++;
        }
        return result;
    }
}