[JAVA] 프로그래머스 풍선터트리기_구현

 

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

프로그래머스

 

 

접근 : 

 

  - 풍선의 갯수가 1인 경우 = 1개만 가능

 

  - 풍선의 갯수가 2 인 경우 = 1개를 제거 할 수 있으므로 2개 가능

 

  - 풍선의 갯수가 3개 이상인 경우

   1. 좌측 중간 우측 으로 나뉠 수 있음

   2. 만약 첫 번째 풍선인 경우 우측의 최소값 1개를 제외하고 나머지는 모두 터트릴 수 있으므로 가능 ( 1개를 제거할 수 있으므로 )

   3. 만약 마지막 풍선인 경우 좌측의 최소값 1개를 제외하고 나머지는 모두 터트릴 수 잇으므로 가능 ( 1개 제거 가능 )

   4. 만약 중간의 풍선인 경우 좌측의 최소값과 우측의 최소값을 기준으로 비교한다.

   4-1. 만약 중간의 풍선이 좌측과 우측의 최소값 보다 작은 경우 = 좌, 우측 풍선 중 1개를 터트리고 1개를 제거하므로 가능

   4-2. 만약 중간 풍선이 좌측 또는 우측 최소 값보다 큰 경우 = 좌우측 중 자신보다 큰 풍선을 터트리고 1개를 제거 하므로 가능

   4-3. 만약 중간 풍선이 좌 우측 최소값 보다 큰 경우 = 불가능

 

-> 해당 인덱스를 기준으로 좌측 과 우측의 최소값을 배열에 저장하여 체크한다.

 

 

 

 

코드 구현 : 

 

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