[Programmers] 풍선 터뜨리기

문제 바로가기

• 인접한 두 개의 풍선을 선택하여 더 큰 값이 적힌 풍선을 터뜨리기
• 단 한 번은 더 작은 값이 적힌 풍선을 터뜨릴 수 있다
• 풍선이 하나 남을 때까지 풍선을 터뜨렸을 때, 최후에 남아있는 것이 가능한 풍선의 개수?

• 일단 가장 작은 값이 적힌 풍선은 무조건 남아있을 수 있다.
• (-20 15 -1) 에서 15의 경우처럼, 가장 작은 값(-20) 반대편에 자신보다 더 작은 값이 존재하면 그 값과 가장 작은 값을 제거하기 위해 더 작은 값이 적힌 풍선을 터뜨리는 시행을 두 번 해야하므로 최후에 남아있을 수 없다.
• 즉, 가장 작은 값 반대편에 더 작은 값이 존재하지 않으면 최후에 남아있을 수 있는 풍선

def solution(a):
    answer = 1
    m = min(a)
    m_idx = a.index(m)
    group1 = a[:m_idx]
    group2 = list(reversed(a[m_idx+1:]))
    
    def compute(group):
        answer = 0
        i = 0
        minn = 1000000000
        while i < len(group):
            if minn > group[i]:
                minn = group[i]
                answer += 1
            i+=1
        return answer

    answer += compute(group1)
    answer += compute(group2)
    
    
    return answer