[programmers/python] 풍선 터뜨리기 – 한 번만 작은 풍선을 터트릴 수 있는 최적화 문제

문제 정리

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

 

1️⃣ 문제 조건

• 인접한 두 풍선을 고를 때, 더 작은 번호의 풍선을 터뜨리는 것은 최대 한 번만 가능하다.
• 이후에는 항상 번호가 더 큰 풍선을 터뜨려야 한다.
• 풍선을 터뜨릴 때마다 빈 자리는 중앙으로 채워진다.
• 풍선 배열에서 마지막까지 남을 수 있는 풍선의 개수를 찾는 것이 목표이다.

2️⃣ 예제
예를 들어, 배열이 [9, -1, -5]라면, 각 풍선은 경로를 따라 최후까지 살아남을 수 있다.
문제에서 제공된 여러 예시와 함께, 이러한 흐름을 여러 번 반복하며 가능한 풍선을 모두 찾는다.

---

첫 번째 접근: 완전탐색의 한계

처음에는 스택/큐를 사용하여 가능한 모든 경로를 탐색하는 완전탐색 방식으로 접근할 수 있다.
그러나 이 문제의 입력 크기는 최대 1,000,000이므로, 모든 경우의 수를 전부 계산하는 것은 불가능하다.
이는 O(2^N) 수준으로 경우의 수가 기하급수적으로 늘어나기 때문이다.

---

효율적인 최적화 아이디어: 양쪽 최소값만으로 판단하기

모든 경로를 확인하지 않더라도, 풍선의 위치를 기준으로 아래의 조건을 확인할 수 있다.

✅ 왼쪽에서의 최소값

• 왼쪽 끝에서부터 해당 풍선까지의 최소값을 저장한다.
• 이 값은 “이 풍선보다 왼쪽에 더 작은 풍선이 있었는지”를 확인해주는 역할을 한다.

✅ 오른쪽에서의 최소값

• 오른쪽 끝에서부터 역순으로 최소값을 저장한다.
• 이 값은 “이 풍선보다 오른쪽에 더 작은 풍선이 있었는지”를 알려준다.

---

핵심 아이디어

풍선 a[i]는
“왼쪽 최소값보다 작거나 같거나” 또는 “오른쪽 최소값보다 작거나 같으면”
반드시 마지막까지 살아남을 수 있다.

이것만 확인하면, 풍선을 직접 하나씩 터뜨려보지 않아도 어떤 풍선이 살아남을 수 있는지 알 수 있다.

---

최종 코드

아래는 최적화된 코드를 기반으로, 명확히 읽기 좋게 정리한 최종 코드이다.

def solution(a):
    n = len(a)
    answer = 0

    # 왼쪽 최소값 배열
    lefts = [0]*n
    lefts[0] = a[0]
    for i in range(1, n):
        lefts[i] = min(lefts[i-1], a[i])
    
    # 오른쪽 최소값 배열
    rights = [0]*n
    rights[-1] = a[-1]
    for i in range(n-2, -1, -1):
        rights[i] = min(rights[i+1], a[i])

    # 각 풍선이 마지막까지 살아남을 수 있는지 확인
    for i in range(n):
        if i == 0 or i == n-1:
            answer += 1
            continue
        if a[i] <= lefts[i-1] or a[i] <= rights[i+1]:
            answer += 1
    
    return answer