[Programmers] Level 3 : 풍선 터트리기

프로그래머스

꽤나 재밌는 문제이다. N개의 풍선이 주어지고, 2개씩 풍선을 비교한다. 이때 큰 값을 가지고 있는 풍선은 사라지는데, 딱 한번 작은 풍선이 먼저 사라지는 경우를 넣을 수 있다고 한다. 제한이 매우 크기 때문에 브루트 포스는 절대 불가능 하고, DP도 아니고...

먼저 양끝 풍선에 대해 관찰 해보면, 이들은 무조건적으로 정답의 후보가 될 수 있다는 것을 알 수 있다. 그래서 '각 풍선을 기준으로 우승자가 될 수 있는지?'로 관점을 바꿔 문제를 접근했다.

하나의 풍선을 마지막 까지 남겨놓고 나머지 풍선들을 우선으로 대결을 시킨다고 생각해보자. 그러면 결국 a, b, c 이런식으로 풍선이 남게 되는데, 우리가 궁금한것은 b가 우승자가 될 수 있는가? 이다. b가 우승자가 되는 경우의 수는 b가 a, c 보다 큰 경우를 제외한 모든 케이스이다. 따라서 b <= a || b <= c를 만족한다면 b는 우승자가 무조건 될 수 있다.

그래서 각 index를 기준으로 [0~index-1] [index+1 ~ size-1]에 위치한 풍선중 최솟값을 찾아야 한다. 그리고 이는 O(N) 연산 2번만 돌리면 배열로 나타낼 수 있다.

import java.util.*;
import java.lang.Math.*;

class Solution {
    private static final int LENGTH = 1000010;
    
    public int solution(int[] a) {
        
        
        int[] mini1 = new int[LENGTH];
        int[] mini2 = new int[LENGTH];
        
        int answer = 0;
        for (int i=0; i<a.length; i++) mini1[i] = a[i];
        for (int i=0; i<a.length; i++) mini2[i] = a[i];
        for (int i=1; i<a.length; i++) mini1[i] = Math.min(mini1[i], mini1[i-1]);
        for(int i=a.length-2; i>=0; i--) mini2[i] = Math.min(mini2[i], mini2[i+1]);
        
        for (int i=1; i<a.length-1; i++) {
            int left = mini1[i-1];
            int right = mini2[i+1];
            if(a[i] <= left || a[i] <= right) answer++;
        }
        
        return answer + 2;
    }
}