문제링크

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

구현방법

구현문제

-> 가장 작은 수의 풍선은 무조건 통과함.

가장 큰 관건 -> 본인보다 작은 수를 한번 터뜨릴 수 있다. -> 가장 작은수를 터뜨리는데 써야한다. (그래야 생존이 가능하기 때문에.)

그렇기 때문에 가장 작은수를 먼저 찾고 가장 작은 수를 기준으로 왼쪽과 오른 쪽을 따로 계산해준다.

why ? 가장 작은수가 왼쪽을 기준으로 봣을때 오른쪽을 다 터뜨려주기 때문에

마찬가지로 가장 작은수 기준으로 오른쪽의 왼쪽 수들은 가장 작은수가 다 터뜨려준다.

-> 결국엔 가장 작은 수의 왼쪽 수들은 본인의 왼쪽 수들을 터뜨릴 수 있는가( 못터뜨리는 경우 최후까지 남을 수 없다. why? 거기서 본인보다 작은수를 만나서 터뜨리면 가장 작은수를 터뜨릴 수 없기 때문에.)

오른쪽도 마찬가지로 진행한다. 각 왼쪽과 오른쪽의 최솟값 갱신과 개수 체크를 하고 마지막에 왼쪽과 오른쪽의 개수를 더해준다.

알고리즘

구현

CODE

class Solution {
    public int solution(int[] a) {
        int answer = 0;

        int min = Integer.MAX_VALUE;
        int min_idx = 0;

        //최소값 갱신및 위치 체크
        for(int idx= 0; idx <a.length;idx++){
            if(min > a[idx]){
                min = a[idx];
                min_idx = idx;
            }
        }

        //가장 작은 수의 인덱스 기준으로 좌 체크
        //가장 끝 값은 가능하다.(존재한다면)
        int left = 0;
        int left_check = 0;
        int left_min = a[left];
        for(int index = left; index < min_idx;index++) {
            if(index == left) {
                left_check += 1;
                continue;
            }
            //왼쪽의 값보다 작은경우
            if(left_min > a[index]){
                left_check+=1;
                left_min = a[index];
            }



        }

        //가장 작은 수의 인덱스 기준으로 우 체크
        //가장 끝값은 가능함(존재한다면).
        int right = a.length-1;
        int right_check = 0;
        int right_min = a[right];
        for(int index = right; index > min_idx;index--) {
            if(index == right){
                right_check+=1;
                continue;
            }

            if(right_min > a[index]){
                right_check+=1;
                right_min = a[index];
            }



        }
        answer = left_check + right_check +1 ;

        return answer;
    }
}