(C#) 풍선 터트리기

코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 스쿨

프로그래머스

 

풍선을 터트리는 문제

 

n번째 풍선을 남기고 싶으면 0~n-1까지의 풍선을 모두 터트리고 n+1~끝까지의 풍선을 모두 터트리면 된다.

[0, n)의 풍선을 모두 터트리다보면 [0, n)에서 최소값을 가지는 풍선만이 남을 것이다.

마찬가지로 (n, 끝)의 풍선을 모두 터트리면 (n, 끝)에서 최소값을 가지는 풍선만이 남을 것이다.

 

인접한 두 풍선 중 작은 풍선을 터트릴 기회는 최대 1번밖에 없으므로, n양쪽에 남은 풍선이 모두 n보다 작다면 n을 남길 수 없을 것이다.

 

처음에는 n번째 풍선의 왼쪽과 오른쪽에 남는 풍선을 일일이 구해서 했다.

for( 0 ~ a.Length)

    for(0 ~ n - 1), for(n+1 ~ a.Length)

-> O(n^2)

-> a의 크기가 최대 100만개이므로 n^2는 시간초과가 나왔다

 

그래서 a[i]에서 왼쪽값, 오른쪽값을 미리 구해놓는 방법으로 했다.

for(0 ~ a.Length)

    left값 구하기

for(0 ~ a.Length)

    right값 구하기

for(0 ~ a.Length)

    풍선이 터트릴 수 있는지 확인하기

-> O(n)

-> 통과

 

코드

using System;

public class Solution {
    public int solution(int[] a) {
        int answer = 2;
        // 어떤 풍선을 남기고싶으면 그 양옆을 다 터트리면 된다 n
        // -> 어떤 풍선의 왼쪽에 있는 모든 풍선 중 가장 작은 풍선 x
        // -> 어떤 풍선의 오른쪽에 있는 모든 풍선 중 가장 작은 풍선 y
        // x, y가 모두 n보다 작으면 불가능
        // x, y가 하나라도 n보다 크면 가능
        var left = new int[a.Length];
        var right = new int[a.Length];
        
        left[0] = int.MaxValue;
        for(var i = 1; i < a.Length; i++){
            left[i] = Math.Min(left[i - 1], a[i - 1]);
        }
        right[a.Length - 1] = int.MaxValue;
        for(var i = a.Length - 2; i >= 0; i--){
            right[i] = Math.Min(right[i + 1], a[i + 1]);
        }
       
        for(var i = 1; i < a.Length - 1; i++){
            // Console.WriteLine($"[{left[i]} {a[i]} {right[i]}]");
            if(a[i] < left[i] || a[i] < right[i]) answer++;
        }
        return answer;
    }
}

결과