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

문제

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

프로그래머스

 

---

 

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int n = a.length;
        if (n < 3) return n;
        
        int[] leftMin = new int[n];
        int[] rightMin = new int[n];
        
        leftMin[0] = a[0];
        rightMin[n-1] = a[n-1];
        
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i-1], a[i]);
        }
        
        for (int i = n-2; i >= 0; i--) {
            rightMin[i] = Math.min(rightMin[i+1], a[i]);
        }
        
        int answer = 2;
        
        for (int i = 1; i < n-1; i++) {
            if (a[i] > leftMin[i-1] && a[i] > rightMin[i+1]) continue;
            answer++;
        }
        
        return answer;
    }
}