[lv3] 풍선 터트리기

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

 

 

생전 처음보는 유형이었다. 그리디하게 풀 수 있다.

 

인접한 풍선을 계속 터트렸을 때, n번째 풍선이 남을 수 있는 경우의 수를 출력하는 문제다.

단, 항상 인접한 풍선 중 숫자가 큰 것을 터트려야 하며, [딱 한번 숫자가 작은 것을 터트릴 수 있다.]

 

배열 사이즈는 최대 100만이므로 완전 탐색은 할 수 없다.

그러므로 약간 dp적 사고?를 하려했고 dp[i][2]로 놓아 각각 예외를 사용했을 경우와 안했을 경우의 최적 값으로 놓으려했다. 적용하려 하니 쉽지 않았다.

 

 

그래서 사고를 바꿨다.

 

1. 왼쪽/오른쪽 부터 탐색했을 때 최솟값을 담은 2개의 배열을 초기화한다.

e.g. l[3] = (idx = 0 to 3까지 탐색했을 때 최솟 값), r[3] = (idx = a.length() -1 to 3까지 탐색했을 때 최솟 값)

 

2. 각 배열의 의미는,  [딱 한 번 숫자가 작은 것을 터트릴 수 있는] 기회를 [사용하지 않았을 때]의 값을 담은 배열이다

(최솟값 이므로, 항상 더 큰 풍선만을 터트려왔을 경우에 해당한다.)

 

3. a[n]이 답인지 확인하려면, l[n-1]과 r[n+1]을 비교한다. 여기서 [기회를 사용]한다.

 

3-1. l[n-1]과 비교하여, 

 

if

n = 0이라면, 왼쪽에 인접한 값이 없으므로 기회를 사용하지 않아도 된다.

 

else

l[n-1] < a[n]라면, 기회를 사용해야 한다.

l[n-1] > a[n]라면, 기회를 사용하지 않아도 된다.

 

3-2. r[n+1]과 비교하여,

 

if

n = a.length() - 1이라면, 오른쪽에 인접한 값이 없으므로 기회를 사용하지 않아도 된다.

 

else

r[n+1] < a[n]라면, 기회를 사용해야 한다.

r[n+1] > a[n]라면, 기회를 사용하지 않아도 된다.

 

4. 기회를 2번 사용해야 한다면, 이는 [답이 될 수 없음]을 의미한다.

다시 말하면, 한 번이라도 기회를 사용하지 않아도 된다면 답임을 의미한다.

 

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        int A = a.length;

        int[] l = new int[A];
        int[] r = new int[A];

        l[0] = a[0];
        r[A-1] = a[A-1];

        for(int i=1; i<A; i++)
            l[i] = Math.min(l[i-1], a[i]);

        for(int i=A-2; i>=0; i--)
            r[i] = Math.min(r[i+1], a[i]);

        for(int i=0; i<A; i++) {
            int now = a[i];

            // 목표가 왼, 오보다 최소한 한번은 작아야 답이다.
            // 왼, 오중 하나라도 인접한 곳이 없다면? 한번은 작다고 취급한다.
            if(i == 0 || l[i-1] > now || i == A-1 || r[i+1] > now)
                answer++;
        }

        return answer;
    }
}