풍선 터뜨리기 - 프로그래머스

풍선 터뜨리기 - 프로그래머스

• 풍선이 끝까지 남기 위해서는 이 풍선보다 작은 풍선이 없거나, 풍선의 왼쪽 오른쪽에 해당 풍선보다 큰 풍선이 존재해야함.
• 반대로 생각했을 때 양끝에서 시작했을 때 자기보다 작은 숫자의 풍선이 있다면 해당 풍선은 남을 수 있는 풍선
• 위와 같이 생각했을 때 양쪽 끝값은 무조건 남길 수 있다.
• 즉, left와 right는 자기보다 작은 숫자가 나타날 때 갱신됨
• 남는 풍선 = left에 갱신된 횟수 + right에 갱신된 횟수 + 양끝값 개수(2) - 1(중복일 경우)

def solution(a):
    ret = 2
    if 0 <= len(a) <= 2:
        return len(a)
    left = a[0]
    right = a[-1]

    for i in range(1, len(a) - 1):
        if left > a[i]:
            left = a[i]
            ret += 1
        if right > a[-1 - i]:
            right = a[-1 - i]
            ret += 1
    if left == right:
        return ret - 1
    else:
        return ret