Programmers - 풍선 터트리기

문제 링크

작은 풍선을 터트리는 기회를 사용하지 않으면 결국 남는 것은 가장 작은 풍선일 것이다.
가장 작은 풍선 이외에 다른 풍선들을 살리고 싶으면 가장 마지막에 작은 풍선을 터트리는 기회를 사용해야 한다.

양 끝에 위치한 풍선은 무조건 생존이 가능하다.
첫번째 풍선을 예로 들면 우선 첫번째 풍선을 제외한 나머지 풍선을 다 터트리면 결국 남는 것은
2번째 풍선 ~ 마지막 풍선 중 최소 값을 가진 풍선이 남을 것이다.
이때 남은 풍선이 더 크면 그냥 터트리면 되고, 작으면 기회를 사용해 터트리면 된다.

양 끝이 아닌 i번 풍선을 터트리는 경우는 다음과 같이 확인할 수 있다.
일단 i번을 제외하고 0번~i-1번, i+1번 ~ 마지막 풍선 을 다 터트린다.
그렇게 되면 min(a[0]~a[i-1]), a[i], min(a[i+1],a[n-1]) 의 3가지 풍선이 남는다.

작은 풍선을 터트릴 수 있는 기회는 한번 뿐이다. i번 양쪽에 남은 풍선들이 모두 i번 풍선보다 작다면
한쪽에 기회를 사용해도 남은 한쪽과 비교했을 때 생존할 수 없다.

이때 min(a[0]~a[i-1])과 min(a[i+1],a[n-1]) 을 매번 구하게 될 경우 시간초과가 발생할 것이다.
따라서 f_min[i]에 0~i번째 까지의 최소 값을 미리 저장해놓고 b_min[i]에 i~n-1번 까지의 최소 값을 미리 저장해 놓으면 O(1)에 원하는 특정 범위의 최소 값을 가져올 수 있고, O(N)에 모든 풍선의 생존 가능 여부를 판단할 수 있게 된다.

def solution(a):
    n = len(a)
    if n <= 2:
        return n
    # 길이 3 이상일 때
    max_value = 1000000000
    # 0 ~ i번째 까지 최소값
    f_min = [max_value for _ in range(n)]
    # i번 ~ n-1번째 까지 최소값
    b_min = [max_value for _ in range(n)]

    f_min[0] = a[0]
    for i in range(1, n):
        f_min[i] = min(f_min[i-1], a[i])
    b_min[n-1] = a[n-1]
    for i in range(n-2, -1, -1):
        b_min[i] = min(b_min[i+1], a[i])

    answer = 2
    for i in range(1, n-1):
        if f_min[i-1] < a[i] and b_min[i+1] < a[i]:
            continue
        answer += 1

    return answer