LV3 풍선 터트리기 (Python)

 

---

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68646

프로그래머스

 

풀이

작은 값은 '한번만' 터트릴 수 있는게 문제의 요점이다.

내가 선택한 풍선이 살아남기 위해서, 내가 가장 작은값이 아니라면 언젠가 가장 작은값을 터트려야한다.

결국 작은값을 터트리는 선택지는 가장 작은 풍선을 만났을때만 사용할 수 있는 것이다. (가장 작은 값을 가진 풍선은 무조건 살아남을 수 있다.)

 

만약 내가 가장 작은값 왼쪽에 존재한다고 해보자, 내 오른쪽은 가장 작은 값의 풍선이 모두 터트려줄 수 있다. 그러나 내 왼쪽은 내가 모두 터트려야한다. 그 뜻은, 내 왼쪽에는 나보다 큰값만 존재해야 한다는 것이다. 만약 작은값이 하나라도 있어서 작은 풍선을 터트리는 기회를 그 풍선에게 사용한다면, 오른쪽에 존재하는 가장 작은 풍선을 터트릴 수 없기 때문이다.

 

예로

[7, 10, 1, 15] 와 같은 값이 있다고 생각해보자.

 

7은 가장 작은값인 -10의 왼쪽 편에 위치한다. 그리고  7왼쪽으로는 따로 터트릴 풍선이 없고, 그 오른쪽은 1이 다 터트릴 수 있다. 따라서 살아남을 수 있다.

 

10같은 경우에도 1의 왼쪽에 존재한다. 자신의 오른쪽은 1이 알아서 없애줄테고, 자신의 왼쪽만 자신의 힘으로 터트릴 수 있으면 된다. 그러나 7은 10보다 작다. 따라서 7을 터트리면 오른쪽의 가장 작은값인 1을 터트릴 기회를 지닐 수 없다. 따라서 10은 살아남을 수 없다. (단순히 말하면, 내 왼쪽으로 나보다 작은값이 있으니 살아남을 수 없다.)

 

...

 

이런식으로 가장 작은값 기준으로 왼쪽 오른쪽을 나누어서 몇개가 살아남을 수 있는지 체크하면 풀 수 있다. 

 

코드

import sys

def solution(a):
    front = 0
    back = len(a) - 1
    minVal = min(a)
    answer = 1 # min 값

    # minVal 왼쪽
    rangeMin = sys.maxsize
    while a[front] != minVal:
        if a[front] < rangeMin:
            rangeMin = a[front]
            answer += 1
        front += 1
            

    # minVal 오른쪽
    rangeMin = sys.maxsize
    while a[back] != minVal:
        if a[back] < rangeMin:
            rangeMin = a[back]
            answer += 1
        back -= 1
            
    return answer

 

후기

 

아이디어가 생각이 안나서 고민하다 질문탭을 보고 아이디어를 얻어 구현했다. 이런 생각은 어떻게 하는건가..