[프로그래머스] 풍선터트리기 (파이썬)

난이도 : LV 3

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

문제해결 아이디어

• 문제를 못풀어서 다른사람의 풀이를 참고하고 풀었다.
• 문제의 핵심 아이디어는 해당위치를 기준으로 왼쪽의 최솟값과 오른쪽의 최솟값 둘중 하나라도 해당위치의 수보다 크면 끝까지 살아남을 수 있다는 것.
• 거기다가 단순 리스트 슬라이싱과 min함수를 사용하면 시간초과가 나기 때문에
• 왼쪽을 기준으로 각 인덱스까지의 최솟값을 담은 배열과 오른쪽을 기준으로 각 인덱스 까지 최솟값을 담은 배열을 생성한 후 비교해준다.

소스코드

def solution(a):
    ans = 2 # 기본적으로 양끝은 무조건 살아남을수 있다.
    
    left_min = [a[0]]
    right_min = [a[-1]]
    
    for i in range(1, len(a)):
        if left_min[-1] > a[i]:
            left_min.append(a[i])
        else:
            left_min.append(left_min[-1])
            
        if right_min[-1] > a[len(a)-1-i]:
            right_min.append(a[len(a)-1-i])
        else:
            right_min.append(right_min[-1])
    
    right_min.reverse() # 계산을 편하게 하기위해서
    
    for i in range(1, len(a)-1):
        if left_min[i-1] > a[i] or right_min[i+1] > a[i]:
            ans += 1
    return ans