[프로그래머스] 풍선 터트리기, Python3

문제는 여기!

 

안녕하세요! 이번 포스팅에서는 프로그래머스의 "월간 코드 챌린지 시즌1" 문제였던 풍선 터트리기 문제를 풀어볼까 합니다. 항상 "이 문제는 어떤 알고리즘으로 풀지?" 라고 생각하다가 신박한 방법이 필요했던 문제라서 이번 포스팅에서 정리해보았습니다. 스스로 완벽하게 해결하지는 못했던 문제였어서 다른 풀이들을 많이 참조했습니다. 바로 가보시죠!

제한사항 및 주의사항

임의의 인접한 두 풍선을 고르고 두 풍선중 하나를 터트릴 경우, 번호가 작은 풍선은 한번만 터트릴 수 있습니다. 이를 제외하면 번호가 큰 풍선만 터트릴 수 있습니다. 작은 풍선을 터트리는 경우를 저는 찬스라고 표현해보겠습니다.

풍선 리스트 a의 크기는 1 ~ 1,000,000 이며, a[i]의 크기는 -10억 이상 ~ 10억 이하인 정수입니다.

풀이전략

이 문제는 O(n)으로 풀어야 한다고 해설에 나와있으며, O(n)으로 풀기 위해서는 효율적으로 풀기 위한 방법을 찾아야합니다.

일단 제일 사이드쪽(a[0], a[-1])과 최솟값은 반드시 살아남을 수 있습니다. 첫 번째로 사이드의 풍선은 사이드를 제외한 나머지 풍선들끼리 터트리고 나서 마지막으로 a[0] 혹은 a[-1] 풍선(이하 사이드 풍선)과 살아남은 어떤 a[i] 풍선 (이하 생존 풍선)이 남아있다고 가정해봅시다. 생존 풍선의 값이 크던 작던 우리는 찬스가 남아있기에 사이드 풍선은 무조건 살아남을 수 있죠.

두 번째, a 리스트의 최솟값 번호 풍선의 경우는 찬스를 아예 안쓰고 살아남을 수 있습니다.어차피 번호가 큰 풍선만 터트리기 때문입니다.

그럼 이제 나머지 경우들을 살펴봐야 합니다. 원소들을 1번째 ~ len(a) - 1 까지 순회합니다. 문제에서 주어진 두 번째 예시와 함께 그림으로 같이 살펴볼게요.

a[1]인 27부터 살펴보겠습니다. a[1]의 왼쪽에는 -16만이 남아있고, 오른쪽은 65부터 -33까지 남아있습니다. 결론부터 말씀드리면 27은 살아남을 수 없습니다.

27의 오른쪽 원소들을 다 터트려서 -92만 남았다고 가정해보겠습니다.

여기서 27은 -16, -92보다 크기 때문에 찬스를 한번 쓰더라도 무조건 터집니다. 이젠 반대로 살아남을 수 있는 풍선의 예시를 들어보겠습니다. min(a)인 -92로요!

-92는 살아남을 수 있습니다. 왼쪽, 오른쪽의 살아남은 풍선 모두 -92보다 크기 때문에 찬스를 쓰지 않고도 자신보다 큰 두 풍선을 빵빵 터트려주면 됩니다.

마지막으로 찬스를 한번 써야되는 경우를 살펴보겠습니다.

-71은 살아남을 수 있습니다. -68을 찬스 없이 터트려주고, -92를 찬스를 써서 터트리면 -71은 살아남을 수 있습니다.

여기서 결론을 내릴 수 있습니다. 살아남을 수 있는 경우는 앞서 말씀드렸던 i = 1부터 len(a)-1 까지 순회할 때, a[i] 기준 왼쪽, 오른쪽에서 살아남은 풍선들보다 값이 크면 a[i] 풍선은 살아남을 수 없습니다.

그 외의 경우, a[i]가 왼쪽, 오른쪽에서 살아남은 풍선들 보다 작은 경우는 찬스를 쓰지 않아도 살아남을 수 있고, 왼쪽에서 살아남은 풍선 혹은 오른쪽에서 살아남은 풍선 중 하나보단 크더라도 찬스를 이용해서 살아남을 수 있다는 점을 알 수 있습니다.

코드 해설

def solution(a):
    answer = 0
    min_idx = a.index(min(a))
    left = a[:min_idx]
    right = reversed(a[min_idx + 1:])

    left_min = 1000000001
    right_min = 1000000001
    for l in left:
        if left_min > l:
            left_min = l
            answer += 1

    for r in right:
        if right_min > r:
            right_min = r
            answer += 1

    return answer + 1

min_idx에는 a리스트의 최솟값이 위치한 인덱스를 저장합니다.

left, right는 최솟값 인덱스를 기준으로 왼쪽, 오른쪽을 나누었습니다. 시간 복잡도 O(n)으로 풀기 위한 셋팅이라고 보시면 될 것 같아요. 그리고 문제에서 a[i]의 크기는 10억 이하라 했으므로 미리 left_min, right_min에 10억 + 1을 저장해두었습니다.

right은 왜 reverse 처리 하셨나요?

앞에서 사이드(a[0], a[-1])는 항상 살아남을 수 있다. 라고 했습니다. 사이드부터 풍선이 살아남을 수 있는지 판별해야하기에 right는 reverse처리했습니다.

left, right의 원소들 마다 최솟값을 만나게 되면 answer를 + 1 해줍니다. 그리고 마지막은 answer에 1을 더하여 리턴합니다. 풍선 리스트에서 가장 최솟값은 살아남을 수 있으니 +1 했습니다.

오늘의 풀이는 여기까지입니다. 혹여나 제가 틀린 방식으로 설명했을 경우는 가감없이 피드백 부탁드립니다.