[프로그래머스 Lv.3] 풍선 터트리기 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68646

프로그래머스

풀이

dp에서 사용하는 메모이제이션을 통해 최솟값을 저장하는 방법으로 문제를 풀이하였다.

 

이 문제를 풀이하긴 위해서 풍선을 마지막까지 남길 수 있는 조건이 무엇인가를 알아야 한다.

문제의 조건을 간단하게 요약하면 남기려고 하는 풍선의 좌우에 위치한 남은 풍선 중 하나라도 크기만 하면 된다는 것이다.

그렇기에 남기려고 하는 풍선의 좌측에 남은 풍선들의 최솟값이나 우측에 남은 풍선들의 최솟값 중 하나라도 크면 된다.

 

실제로 이 가설이 맞는지 확인해보도록 하자.

1. [9, 3, 1]일 때 3을 남기려고 시도해 보겠다. => 9와 3을 비교하여 더 큰 9를 터뜨린다. [3, 1] => 3과 1을 비교한 후 번호가 더 작은 풍선을 터뜨리는 기회를 사용하여 1을 터뜨린다. 3을 남기는 데 성공하였다.
2. [1, 3, 2]일 때 3을 남기려고 시도해 보겠다. => 1과 3을 비교한 후 번호가 더 작은 풍선을 터뜨리는 기회를 사용하여 1을 터뜨린다. [3, 2] => 3과 2에서 최종적으로 3을 남기기 위해선 2를 터뜨려야 하지만 이미 더 작은 풍선을 터뜨리는 기회는 소진되었으므로 3이 터지는 경우 밖에 남지 않는다.

위의 예시를 통해 가설이 성립함을 확인할 수 있다. 이제 이 가설을 구현하기 위해, 또 메모이제이션을 통해 O(n)의 시간복잡도 안에 해결할 수 있도록 코드를 작성하면 된다.

def solution(a):
    if len(a) == 1:
        return 1
    
    answer = 2 # 맨 끝에 위치한 풍선들은 찬스를 사용할 수 있기에 무조건 남길 수 있다.
    
    l_min = [a[0]] # 0번 인덱스부터의 최솟값들을 담아갈 배열
    r_min = [a[-1]] # len(a)-1번 인덱스부터의 최솟값들을 담아갈 배열
    
    for i in range(1, len(a)): # 순회하며 각 인덱스에서의 좌우의 최솟값을 각각의 배열에 갱신하기
        l_min.append(l_min[i-1] if l_min[i-1] < a[i] else a[i])
        r_min.append(r_min[i-1] if r_min[i-1] < a[len(a)-i-1] else a[len(a)-i-1])
        
    r_min.reverse() # 0번 인덱스부터 시작할 수 있도록 배열을 역순으로 변경
    
    for i in range(1, len(a)-1): # 맨 끝에 위치한 풍선들을 제외하고 순회하며
        if a[i] < l_min[i-1] or a[i] < r_min[i+1]: # 남기려고 시도하는 풍선이 좌우의 최솟값 풍선 중 하나보다 더 작으면
            answer += 1 # 남길 수 있는 풍선임
    
    return answer