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

문제 설명

어느 배열이 주어지고 이 배열에서 숫자를 하나씩 지워갈 때 마지막에 남을 수 있는 숫자의 개수를 구하는 문제입니다. 배열에서 숫자를 삭제할 때는 인접한 두 숫자를 비교해서 더 큰 숫자를 삭제합니다. 단 1회에 한해서 더 작은 숫자를 삭제할 수 있습니다.

작동 순서

1. 배열의 순서별로 자신의 왼쪽에 자신보다 작은 숫자가 있는지 확인합니다.
2. 배열의 순서별로 자신의 오른쪽에 자신보다 작은 숫자가 있는지 확인합니다.
3. 만약 한 숫자의 양쪽 모두 자신보다 작은 숫자가 있는 경우 이 숫자는 마지막까지 남을 수 없습니다. 현재 숫자를 기준으로 양쪽에서 각각 연산을 해가며 큰 숫자들을 삭제하면 최종적으로 현재 숫자의 양옆에 자신의 왼쪽에서 가장 작은 수, 자신의 오른쪽에서 가장 작은 수가 남게 됩니다. 이때 만약 자신보다 작은 수가 1개 이하이면 그 숫자를 삭제할 수 있지만 양쪽 모두 자신보다 작은 경우 두 수를 비교해서 작은 숫자를 한번 삭제하더라도 자신보다 작은 수가 남으므로 마지막에 남는 것이 불가능합니다.
4. 만약 한 숫자의 양쪽 모두 자신보다 크거나 한쪽만 자신보다 큰 경우 자신보다 작은 숫자 하나만 삭제하고 자신이 마지막에 남는 것이 가능하므로 answer를 +1 해줍니다.
5. 모든 연산이 끝나면 answer를 출력합니다.

소스코드

def solution(a):
    answer = 0
    length=len(a)
    arr = [0]*length
    minNum=1e11
    for i in range(length):
        if minNum>a[i]:
            arr[i]+=1
            minNum=a[i]
    
    minNum=1e11
    for i in range(length-1, -1, -1):
        if minNum>a[i]:
            arr[i]+=1
            minNum=a[i]
    
    for i in arr:
        if i!=0:
            answer+=1
    return answer