[프로그래머스 Lv. 3] 풍선 터뜨리기

문제

https://programmers.co.kr/learn/courses/30/lessons/68646?language=python3

접근

1. 풍선을 자기 오른쪽과 비교해서 더 작은 풍선을 할당한 배열을 prerix, 자기 왼쪽과 비교한 배열을 suffix로 둔다.

2. 풍선 배열의 길이만큼 반복문을 돌아 현재 풍선의 크기와 풍선의 인덱스와 동일한 prefix, suffix를 비교한다. 풍선이 하나만 남는 조건은 prefix[i] == balloon[i] == suffix[i] 이거나 prefix, suffix 중 하나는 반드시 풍선보다 작아야 한다.

   예시) [-16,27,65,-2,58,-92,-71,-68,-61,-33]인 풍선의 prefix는 [-16, -16, -16, -16, -16, -92, -92, -92, -92, -92] suffix는 [-92, -92, -92, -92, -92, -92, -71, -68, -61, -33]다.

   이 때 -16은 -92 <= -16 <= -16을 만족한다. 문제 조건에서 자신보다 작은 풍선 하나는 터트릴수 있다고 했으므로 -92 풍선을 터트리면 -16은 혼자 남겨져 정답이 된다.

   반면에 27은 -16보다 크면서 -92보다 크다. 이 때 -16을 터뜨리든 -92를 터뜨리든 27은 어떠한 풍선보다 크므로 반드시 터지게 된다.

Code

def solution(a):
    answer = 0
    prefix, suffix = [0]*len(a), [0]*len(a)
    prefix[0], suffix[0] = a[0], a[-1]
    
    for i in range(1, len(a)):
        prefix[i] = min(prefix[i-1], a[i])
        suffix[i] = min(suffix[i-1], a[-1-i])
    suffix = suffix[::-1]
    
    for i in range(len(a)):
        if prefix[i]<= a[i] <= suffix[i] or suffix[i] <= a[i] <= prefix[i]:
            answer+=1
    
    return answer

여담

회사에서 준 과제 다하고 너무 심심해서 풀은 문제. 이런 문제들은 구현 자체는 쉬운데 아이디어 내는데 너무 어려운 것 같다.