[프로그래머스] 풍선 터뜨리기 / Python

문제주소 :programmers.co.kr/learn/courses/30/lessons/68646

코딩테스트 연습 - 풍선 터트리기

---

<문제 설명>

문제 설명

일렬로 나열된 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                                                                        result

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

---

입출력 예 설명

입출력 예 #1

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

입출력 예 #2

• 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

 

<풀이법>

▒ 한줄 개념: 양쪽의 최솟값 중 하나라도 나보다 크면 됨! ▒ 

끝까지 남을 수 있는 풍선의 조건은 자신을 기준으로 양쪽의 최솟값 중 하나라도 자신보다 크면 된다는 것입니다.

뒤집어 말하면, 양쪽의 최솟값이 둘 다 자신보다 작다면, 그 풍선은 어떻게든 터질 수 밖에 없다는 것이죠.

예를 들어보겠습니다.

 

1. [10, 9, 11] 의 경우 9는 살아남을 수 있다. (양쪽의 최솟값이 둘 다 자신보다 큰 경우)
   • case 1:
     • 10 ? 9 : 10 펑! -> [9, 11]
     • 9 ? 11 : 11 펑! -> [9]
   • case 2:
     • 9 ? 11 : 11 펑! -> [10, 9]
     • 10 ? 9 : 10 펑! -> [9]
2. [10, 9, 8] 의 경우 9는 끝까지 살아남을 수 있다. (한쪽이라도 최솟값이 자신보다 큰 경우)
   • case 1:
     • 10 ? 9 : 10 펑! -> [9, 8]
     • 9 ? 8 : 8 펑! (나보다 작은 놈 죽이기 찬스 사용!) -> [9] 
   • case 2:
     • 9 ? 8 : 8 펑! (찬스 사용!) -> [10, 9]
     • 10 ? 9 : 10 펑! -> [9]
3. [7, 9, 8] 의 경우 9는 끝까지 살아남을 수 없다. (양쪽 모두 최솟값이 자신보다 작은 경우)
   • case 1:
     • 7 ? 9 : 7 펑! (찬스 사용!) -> [9, 8]
     • 9 ? 8 : 9 펑! (찬스 사용 불가능..) -> [8] 
   • case 2:
     • 9 ? 8 : 8 펑! (찬스 사용!) -> [10, 9]
     • 7 ? 9 : 9 펑! (찬스 사용 불가능..) -> [7]

 

위 예시를 통해 양쪽의 최솟값 중 하나라도 자신보다 클 경우 끝까지 남을 수 있음을 확인할 수 있습니다.

이제 여기서, 만약 기본적인 min()함수 등을 이용해서 양쪽의 최솟값을 일일히 계산하려고 한다면, 시간이 너무 오래걸려 효율성 테스트를 통과할 수 없게됩니다.

따라서 memoization 방식을 이용해서, 왼쪽, 오른쪽의 최솟값을 차례차례 쌓아둔다면, 효율성 테스트도 간단하게 통괗라 수 있습니다.

 

 

이렇게 만들어둔 배열을 통해 빠르게 최솟값에 접근함으로서 효율성 테스트 또한 통과할 수 있습니다.

 

<코드(Python)>

def solution(a):
    if len(a) == 1:
        return 1

    answer = 2   # 기본적으로 양쪽 끝은 끝까지 살아남을 수 있음
    
    # 최솟값 쌓기 ----------------
    l_min = [a[0]]     
    r_min = [a[-1]]
    for i in range(1, len(a)):
        if a[i] < l_min[-1]:
            l_min.append(a[i])
        else:
            l_min.append(l_min[-1])
        if a[len(a) - 1 - i] < r_min[-1]:
            r_min.append(a[len(a) - 1 - i])
        else:
            r_min.append(r_min[-1])
    r_min.reverse()    
    # -----------------

	# 찾은 최솟값으로 비교 계산 -------------
    for i in range(1, len(a) - 1):
        if l_min[i - 1] > a[i] or r_min[i + 1] > a[i]:
            answer += 1
    # --------------------------------
            
    return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest