프로그래머스 풍선 터뜨리기 파이썬 풀이

풍선 터뜨리기 (Lv.3)

문제 요구사항

• 다음 과정을 반복하면서 1개의 풍선을 남긴다.
  1. 임의의 인접한 두 풍선을 선택하고, 두 풍선 중 하나를 터뜨린다.
  2. 터진 풍선으로 인해 빈 공간이 생겼다면, 풍선들을 밀착하여 빈 공간을 없앤다.
• 두 풍선 중 번호가 더 작은 풍선을 터뜨리는 행위는 1번만 할 수 있다.
  • 예외조건이라 하겠다.
• 마지막까지 남을 수 있는 풍선의 개수를 반환하라.
• a의 모든 수는 서로 다르다.

아이디어

문제를 처음에 읽다보면 DP문제 같은 느낌을 받지만 천천히 생각해보면 규칙이 보인다.

결론을 말하자면 무조건 마지막까지 남을 수 있는 가장 작은 수를 기준으로 좌, 우로 나누면 문제를 풀기 편하다.

자세히 적어보겠다.
a의 원소인 a[i]가 마지막까지 남을 수 있는지 판단하려고 한다.
이 때, a[i]를 기준으로 왼쪽, 오른쪽을 나누어 생각해본다.

1. a[i]가 왼쪽과 오른쪽 둘 모두에서 가장 작은 값인 경우
   answer +=1
2. a[i]가 왼쪽과 오른쪽 둘 중 하나에서만 가장 작은 값인 경우
   예외 조건 때문에 answer += 1
3. a[i]가 왼쪽과 오른쪽 둘 모두에서 가장 작은 값이 아닌 경우

가장 작은 수를 기준으로 왼쪽, 오른쪽을 나눈 이유는
a[i]의 입장에서 가장 작은 수가 있는 쪽을 예외 조건으로 터뜨리고 나머지 한쪽만 확인하기 위함이다.

파이썬 코드

from math import inf
def solution(a):
    answer = 0
    min_index = a.index(min(a))
    answer += 1
    
    l_min = inf
    for i in range(min_index):
        if a[i] < l_min:
            l_min = a[i]
            answer += 1
    
    r_min = inf
    for i in range(len(a)-1, min_index, -1):
        if a[i] < r_min:
            r_min = a[i]
            answer += 1
    
    return answer

나는 문제의 입출력 예에서 힌트를 얻었는데 이건 실전에서 도움이 안될 수도 있다.
구체적인 예를 스스로 생각하거나 일반화된 논리로 문제를 푸는 것을 연습 해야겠다.