[pro] 프로그래머스 level3 68646 풍선 터뜨리기 (Java) - 시뮬레이션

[문제]

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

프로그래머스

 

[풀이]

i번째 풍선이 존재하고, 그 양 옆으로 큰 풍선들을 터뜨려나가면 i번째 풍선 양 옆에는 왼쪽 최솟값을 가진 풍선과 오른쪽 최솟값을 가진 풍선이 남을 것이다.

번호가 더 작은 풍선을 터뜨릴 수 있는 기회는 딱 1번 존재하기 때문에, 만약 양 옆 풍선이 둘 다 i번째 풍선보다 더 작으면 i번째 풍선만 남기는 것이 불가능하다. 하나만 더 크거나 둘 다 크면 남기는 것이 가능하다.

맨 왼쪽 풍선과 오른쪽 풍선 같은 경우 한쪽 방향의 최솟값 풍선만이 남게 되고, 그 풍선이 더 작더라도 작은 풍선을 터뜨릴 수 있는 기회가 있기 때문에 해당 풍선만 남기는 것이 항상 가능하다.

따라서 answer=2로 설정해놓고, i번째 풍선에 대한 왼쪽 최솟값, 오른쪽 최솟값 풍선을 저장한 뒤 비교해서 구할 수 있다.

 

[코드]

 

class Solution {
    public int solution(int[] a) {
        int answer = 2; //맨 왼쪽, 오른쪽은 전부 가능
        
        //풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return
        int[] left = new int[a.length];
        int[] right = new int[a.length];
        
        //i일 때 왼쪽 최솟값 저장
        int min = a[0];
        for(int i=1; i<a.length-1; i++){
            left[i] = min;
            if(a[i] < min){
                min = a[i];
            }
        }
        
        //i일 때 오른쪽 최솟값 저장
        min = a[a.length-1]; 
        for(int i=a.length-2; i>0; i--){
            right[i] = min;
            if(a[i] < min){
                min = a[i];
            }
        }
        
        //양 옆의 최솟값이 둘 다 i 보다 작으면 불가능.
        for(int i=1; i<a.length-1; i++){
            if(left[i] < a[i] && right[i] < a[i]) continue;
            answer++;
        }
        
        return answer;
    }
}