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

programmers.co.kr/learn/courses/30/lessons/68646

코딩테스트 연습 - 풍선 터트리기

문제풀이

보자마자 완탐하면 되지 않을까? 했지만 제한 사항 "a의 길이는 1 이상 1,000,000 이하입니다."를 보고 바로 포기했다.

이 문제는 접근을 다르게 가야되지 않을까 생각하게 되었고, 문제 문구중에 "인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다."를 보고 문득 각 풍선마다 왼쪽중에 젤 작은거 오른쪽 중에 젤 작은거를 를 하나씩 남겨 자기와 비교를 하여 터트리는 행위 최대 1번을 넘겨버리면 그 풍선은 마지막까지 남는게 불가능하다고 생각 되었다.

 

leftArr와 rightArr를 따로 선언하여 각각 값을 갱신하였고, 전체 풍선을 도는 for문을 통해 각각 위의 글 문단에서 말한 조건대로 살아남는 풍선을 answer++ 해주었다.

코드

class Solution {
   public static int solution(int[] a) {
        int answer = 0;
        
        int[] leftArr = new int[a.length];
        int leftMin = a[0];
        leftArr[0] = a[0];
        int[] rigthArr = new int[a.length];
        int rightMin = a[a.length-1];
        rigthArr[a.length-1] = a[a.length-1];
        
        for(int i = 0; i<a.length-1; i++) {
        	if(a[i+1] < leftMin) {
        		leftMin = a[i+1];
        	}
        	leftArr[i+1] = leftMin;
        }
        
        for(int i = a.length-1; i>0; i--) {
        	if(a[i-1] < rightMin) {
        		rightMin = a[i-1];
        	}
        	rigthArr[i-1] = rightMin;
        }
        
        for(int i =1; i<a.length-1; i++) {
        	int select = a[i];
        	boolean chance = false;
        	int r = rigthArr[i+1];
        	int l = leftArr[i-1];
        	
        	
        	if(l < select) {
        		chance = true;
        	}
        	
        	if(r < select && !chance) {
        		answer++;
        	}
        	else if(r > select) {
        		answer++;
        	}
        }
        
        return answer+2;
    }
}