프로그래머스 풍선 터트리기

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

개인적으로 문제의 규칙을 찾기가 어려웠다.
문제 해결방안은 먼저 최후에 까지 남을 수 있는 조건은 어떤것인가를 생각해보는 것 이었다.

예를들어 3 5 4라면 5는 어떤 수를 쓰더라도 반드시 지워질 수 밖에 없다.
그러므로 어떤 특정값에 대해 왼쪽의 값이나 오른쪽의 값중 특정값보다 작은 수가 하나는 존재해야 최후까지 남길 수 있다.

시간초과가 났던 코드

def solution(a):
    stack = []
    answer = 2
    for i in range(1,len(a)-1):
        if min(a[0:i]) < a[i] and a[i] > min(a[i+1:]):
            continue
        answer += 1
    return answer

처음에는 왼쪽의 최솟값과 오른쪽의 최솟값보다 큰 경우를 pass하고 답을 하나씩 더해가는 방식을 선택했지만 시간초과가 났다.

그래서 왼쪽이나 오른쪽 어느 한쪽중에 큰값이 있다면 값을 더해가는 방식을 선택하였다.

def solution(a):
    stack = []
    answer = 2
    left = a[0]
    right = a[-1]
    for i in range(1,len(a)-1):
        if left > a[i]:
            answer += 1
            left = a[i]
        if right > a[-1-i]:
            answer += 1
            right = a[-1-i]
    if left == right:
        return answer - 1
    else:
        return answer