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

🔗 문제

 

 

👨🏻‍💻 풀이 및 코드

 

이 문제의 핵심은 번호가 작은 풍선은 1번만 터트릴 수 있기 때문에,

현재 풍선을 기준으로 왼쪽에 인접한 풍선과 오른쪽에 인접한 풍선 모두 현재 풍선보다 번호가 작은 풍선이 있다면 현재 풍선은 끝까지 살아남을 수 없습니다. 

이 원칙을 사용한 구현 방법은

• 현재 인덱스를 기준으로 왼쪽 풍선들 중 가장 작은 번호의 풍선 번호를 구하고, 오른쪽 풍선들 중 가장 작은 번호를 구합니다.
  가장 작은 번호를 구하는 이유는 큰 풍선들만 터트렸을 때 가장 작은 번호만 남게 되기 때문입니다.

 

예제 2) 

주어진 배열

0	1	2	3	4	5	6	7	8	9
-16	27	65	-2	58	-92	-71	-68	-61	-33

 

현재 인덱스를 기준으로 왼쪽 풍선들 중 가장 작은 번호

0	1	2	3	4	5	6	7	8	9
X	-16	-16	-16	-16	-16	-92	-92	-92	-92

 

현재 인덱스를 기준으로 오른쪽 풍선들 중 가장 작은 번호

0	1	2	3	4	5	6	7	8	9
-92	-92	-92	-92	-92	-17	-68	-61	-33	X

 

 

• 각 배열을 돌면서,현재 풍선의 번호가 왼쪽에서 가장 작은 번호의 풍선보다도 작고, 오른쪽에서 가장 작은 번호의 풍선보다 작을 경우만 살아남지 못합니다.
  단, 맨 왼쪽과 맨 오른쪽 풍선은 비교할 풍선이 1개뿐이므로 항상 살아남습니다.

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int[] left = new int[a.length]; //i일때 왼쪽 원소들 중 최솟값
        int[] right = new int[a.length];//i일때 오른쪽 원소들 중 최솟값
        
        int minLeft = a[0];             //왼쪽에서 가장 작은 값, 가장 왼쪽 원소로 초기화
        int minRight = a[a.length-1];   //오른쪽에서 가장 작은 값, 가장 오른쪽 원소로 초기화
        
        //맨 왼쪽은 제외 (왼쪽에 자신보다 더 작은 값은 없으므로)
        for(int i=1; i<a.length; i++) {
            if(a[i] < minLeft) {
                minLeft = a[i];
            }
            left[i] = minLeft;
        }
        
        //마찬가지로 맨 오른쪽은 제외 (오른쪽에 자신보다 더 작은 값은 없으므로)
        for(int i=a.length-2; i>0; i--) {
            if(a[i] < minRight) {
                minRight = a[i];
            }
            right[i] = minRight;
        }
        
        if(a.length ==1) return 1;
        
        int answer = 2; //맨 왼쪽과 맨 오른쪽은 항상 살아 남는다. (비교할 풍선이 1개밖에 없으므로)
        //맨왼쪽과 맨오른쪽을 제외한 풍선들 검사 
        for(int i=1, size=a.length-2; i<=size; i++) {
            if(a[i] > left[i] && a[i] > right[i]) continue;   //현재 풍선보다 왼쪽, 오른쪽이 둘 다 작다면 살아남을 수 없음
            answer++;
        }
        
        return answer;
    }
}