[프로그래머스] 풍선 터드리기

문제

• n개의 풍선을 1개가 남을 때까지 터트리려고 한다.
• 두 개의 인접한 풍선 중 번호가 더 큰 풍선을 터트린다. 단 한 번 더 작은 번호의 풍선을 터뜨릴 수 있다.
• 최후까지 남기는 것이 가능한 풍선의 개수 리턴하기
• 1 <= 풍선 개수 <= 1,000,000

풀이

• 완전 탐색은 1000000! 이상이 되므로 불가능하다.
• 우선 가장 작은 숫자는 무조건 남길 수 있다. 그리고 가장 작은 숫자와 비교할 때까지 남길 수 있는 숫자도 남길 수 있다.
• 따라서 양 끝의 숫자는 무조건 남길 수 있다. 양 끝과 비교해 남겨지는 숫자들도 하나씩 남길 수 있다.

 

def solution(a):
    n = len(a)                  # 풍선 개수
    minimum = a.index(min(a))   # 가장 작은 숫자의 위치
    # minimum 위치가 가장 처음 또는 마지막이 아니라면 남길 수 있는 최소 개수는 3개
    # 가장 처음 또는 마지막이라면 최소 개수는 2개가 된다.
    answer = 3 if 0 < minimum < n-1 else 2
    
    # 처음 인덱스부터 마지막까지 남길 수 있는 풍선 개수 세기
    now = a[0]
    for i in range(1, minimum) : 
        if now > a[i] :
            answer += 1
            now = a[i]
    
    # 마지막 인덱스부터 마지막까지 남길 수 있는 풍선 개수 세기
    now = a[-1]
    for i in range(n-2, minimum, -1) :
        if now > a[i] :
            answer += 1
            now = a[i]
        
    return answer

 

 

 

References

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