[Python] 프로그래머스 <풍선 터트리기>

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

프로그래머스

 

def solution(a):
    # 어떻게 해도 앞뒤 끝에 있는 두수는 남길수 있음
    answer = 2 
    # 정방향 (좌->우) 각 자리까지의 최솟값 저장
    dp = [0]*len(a)
    # 역방향 (우->좌) 각 자리까지의 최솟값 저장
    reverse_dp = [0]*len(a)
    dp[0] = a[0]
    reverse_dp[-1] = a[-1]

    for i in range(1,len(a)):
        dp[i] = min(dp[i-1],a[i])
    
    for i in range(len(a)-2,-1,-1):
        reverse_dp[i] = min(reverse_dp[i+1],a[i])
    
    for i in range(1,len(a)-1):
        # i 기준 좌측 최솟값
        left_min = dp[i-1]
        # i 기준 우측 최솟값
        right_min = reverse_dp[i+1]	
        
        # i 기준 양쪽 모두 큰경우 
        if left_min > a[i] and right_min > a[i]:
            answer += 1
        # 한쪽은 크고 다른 한쪽은 작은 경우
        elif right_min < a[i] < left_min or left_min < a[i] < right_min:
            answer +=1
            
    return answer