[프로그래머스] '풍선 터트리기' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [다른 블로그의 풀이]
   
   [Most1 의 풀이]

---

 

문제 설명

 

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

 

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

• a의 길이는 1 이상 1,000,000 이하입니다.
• a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
• a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
• a의 모든 수는 서로 다릅니다.

 

입출력 예

a	return
[9,-1,-5]	3
[-16,27,65,-2,58,-92,-71,-68,-61,-33]	6

 

 

알고리즘 분석

 

처음에는 재귀함수로 풀면 가능할 거라고 생각했지만, a의 길이가 늘어날수록 극단적으로 늘어나는 런타임 시간으로 인해서 실패했다. 그래서 다른 블로그를 참조했다. 

 

• 나의 풀이

def solution1(a):
    answer = set()
    def boom(a, chance):
        a_len = len(a)
        for i in range(a_len):
            new_a, target = a[:i]+a[i+1:] ,a[i]
            if i == 0: min_num = min(a[:i+2])
            else: min_num = min(a[i-1:i+2])
            if a_len == 1:
                answer.add(target)
                return 0
            if target <= min_num:
                if chance: boom(new_a, False)
                else: return 0
            else:
                boom(new_a, chance)
        return 0

    boom(a, True)
    return answer

 

 

[Python] 프로그래머스. 풍선 터트리기 (Level 3)

 

• 다른 블로그의 풀이

import math
def solution(a):
    answer = 0
    left, right = math.inf, math.inf
    maps = [[0 for _ in range(len(a))] for _ in range(2)]
    # 인접한 풍선을 기준으로 큰 풍선을 터트린다 
    # 왼쪽 기준으로, 번호가 작은 풍선을 남기는 경우 
    for i in range(len(a)):
        if left > a[i]:
            left = a[i]
        maps[0][i] = left
	# 오른쪽 기준 
    for i in range(len(a)-1, -1, -1):
        if right > a[i]:
            right = a[i]
        maps[1][i] = right
    
    for i in range(len(a)):
        if a[i] <= maps[0][i] or a[i] <= maps[1][i]:
            answer += 1
            
    return answer

 

위의 코드는 두가지의 규칙을 이용한 풀이로 두 가지 규칙은 다음과 같다.

 

1. 맨 앞, 맨 뒷 풍선은 어떻게든 남길 수 있다. 
2. 가운데에 있는 풍선은 자신을 둘러싼 풍선의 최솟값보다 작다면 남길 수 있다. 

 

• Most1의 풀이

def solution(a):
    answer = 1
    M = min(a) # a의 요소 중 최솟값을 M에 저장 
    for _ in range(2): # 왼쪽, 오른쪽 두 번 확인을 위해 2번 반복 
        m = a[0] a의 첫번째 요소를 m에 저장 
        i = 1
        while m != M: # m과 M(a중의 최소값)이 다를 경우
            if m >= a[i]: # m보다 a[i]가 더 작을 경우 
                m = a[i] # m에 a[i] 값을 대입 
                answer += 1 
            i += 1
        a.reverse() # 거꾸로해서 한번 더 확인 
    return answer

 

이 풀이는 기본적인 면에서는 위의 코드와 같은 기능을 한다. 

차이점이라면 위의 코드는 for문을 3번에 나눠서 문제를 해결했다면, 

이 코드는 한번에 모든 과정을 처리했다.