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

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

코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 (programmers.co.kr)

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

풀이

이 문제의 조건 중 가장 중요한 조건은 '인접한 두 풍선 중에서 번호가 더 작은 풍선을 터뜨리는 행위는 1번만 할 수 있다'라는 조건이다. 즉, 인접한 풍선의 번호가 모두 더 작다면 마지막까지 남을 수 없다는 것이다.

 

그럼 이러한 상황에서 마지막까지 풍선이 남기 위한 조건은 무엇일지 생각해보쟝. 

임의의 풍선을 중심으로 인접한 풍선의 번호가 모두 더 작으면 안된다. 그럼 모든 원소 값을 기준으로 왼쪽, 오른쪽 풍선 번호의 최소값을 찾고 해당 값보다 현재 풍선의 번호가 작지 않도록 하면 된다.

 

왼쪽, 오른쪽 값의 최소값을 찾아야 하는 이유는 풍선을 차례대로 큰값들만 터트린다고 가정하면, 마지막에는 왼쪽에서 가장 작은 번호와 오른쪽에서 가장 작은 번호가 남게 될 것이다. 즉, 이 값들을 현재 풍선 번호와 비교하고 두 값이 모두 작지 않다면 터트려서 하나만 남길 수 있는 풍선이 된다.

 

위와 같은 방법으로 구현하기 위해 왼쪽 원소의 최소값을 저장하는 배열과 오른쪽 원소의 최소값을 저장하는 배열을 만들어주었다. 범위는 아래와 같다(예제 2의 경우).

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

왼쪽 원소의 최소값을 찾을 때에는 인덱스 범위를 1 ~ 9까지,

오른쪽 원소의 최소값을 찾을 때에는 인덱스 범위를 0 ~ 8까지 계산해 주면 된다.

맨 왼쪽일때는 왼쪽 원소 최소값을, 맨 오른쪽일때는 오른쪽 원소 최소값을 구할 필요가 없기 때문이다.

 

즉 맨 왼쪽, 오른쪽은 인접한 번호가 자신보다 작을 수 있는 경우가 최대 하나이다. 그러므로 맨 왼쪽, 오른쪽 원소는 언제나 마지막까지 남을 수 있다. 이러한 특징을 이용하여 반환할 answer의 기본값을 2로 설정해 주면 된다.

 

왼쪽 원소 최소값 배열, 오른쪽 원소 최소값 배열을 완성하고 맨 왼, 오른쪽을 제외한(위의 표에서 노란색 범위) 원소들의 번호가 왼쪽, 오른쪽 최소값보다 모두 작지 않다면 마지막까지 남길 수 있는 풍선이므로 answer++를 해주면 된다.

 

이러한 문제의 유형을 굳이 따지자면 구현, 시뮬레이션 이라고 볼 수 있을 것같다.

 

코드

import java.util.*;
 
class Solution {
    public int solution(int[] a) {
        int[] leftMin = new int[a.length]; //각 인덱스에서 왼쪽 원소의 최소값을 저장
        int[] rightMin = new int[a.length]; //각 인덱스에서 오른쪽 원소의 최대값을 저장
        int l = a[0]; //왼쪽 값 중 최소값
        int r = a[a.length - 1]; //오른쪽 값 중 최소값
        
        //i일때 왼쪽 원소의 최소값을 저장
        for(int i = 1; i < a.length - 1; i++) {
            if(l > a[i]) l = a[i];
            leftMin[i] = l;
        }
        //i일때 오른쪽 원소의 최소값을 저장
        for(int i = a.length - 2; i > 0; i--) {
            if(r > a[i]) r = a[i];
            rightMin[i] = r;
        }
        
        if(a.length == 1) return 1; //원소가 1개면 답은 1이다.
        int answer = 2; // 반환할 값. 원소가 2개 이상일때 무조건 2개 이상은 남게된다.
        for(int i = 1; i <= a.length - 2; i++) {
            if(a[i] > leftMin[i] && a[i] > rightMin[i]) continue;
            answer++;
        }
        return answer;
    }
}