[파이썬] 풍선 터트리기

문제 설명

일렬로 나열된 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개입니다.

 

🎨 나의 풀이

def solution(a) :
    len_a=len(a)
    answer = [0]*len_a  
    answer[0], answer[-1]=1, 1      # 맨끝과 맨앞은 무조건 살아남을 수 있음
    left=a[0]
    right=a[-1]

    for i in range(1, len_a-1) :
        if a[i] < left :
            answer[i]=1
            left=a[i]
        if a[-1-i] < right :
            answer[-1-i]=1
            right=a[-1-i]

    return answer.count(1)

양쪽에서 탐색(-> <-)

왼쪽 또는 오른쪽에 더 큰 풍선이 있으면 살아남을 수 있다.

 

 

🎋 다른사람 풀이

import heapq

def solution(a):
    balloons = [(b, i) for i, b in enumerate(a)]
    result = len(a)
    left, right = balloons[:1], balloons[1:]
    heapq.heapify(left)
    heapq.heapify(right)

    NUM, IDX = 0, 1
    for i, ballon in enumerate(a[1:-1], 1):
        if ballon == right[0][NUM]:
            while right[0][IDX] <= i:
                heapq.heappop(right)
        if ballon > left[0][NUM] and ballon > right[0][NUM]:
            result -= 1
        heapq.heappush(left, (ballon, i))
    return result

풍선을 남기는 것이 불가능한 경우는 왼쪽에 있는 풍선들의 최소값이 현재 풍선값 보다 작고,
오른쪽에 있는 풍선들의 최소값도 현재 풍선값 보다 작을 때이다.
맨 왼쪽의 풍선과 맨 오른쪽의 풍선은 항상 남는 것이 가능하므로 두번째 풍선부터 마지막에서 두번째 풍선까지 탐색을 한다.
시간 복잡도 문제때문에 heap을 사용하는데, 이 때 오른쪽에 있는 풍선들의 처리를 위해 idx를 함께 저장해준다.

 

balloons는 (값, 인덱스)로 이루어진 리스트다.

enumerate(a[1:-1], 1)에서 1은 시작값이다. 시작값 1이 없으면 i는 0부터 시작되기 때문이다.

ballon이 큰 값이면( ballon > left[0][NUM] and ballon > right[0][NUM]) result를 1감소시킨다.

비교가 끝난 값은 힙left에 튜플형태로 추가한다.

 

if ballon == right[0][NUM]:
            while right[0][IDX] <= i:
                heapq.heappop(right)

 

heap이 작은 값부터 정렬인데 튜플이라 그런지 꼭 그렇지가 않네?

balloon은 리스트 a의 값이고 right는 힙이다. balloon==right[0][NUM]이면 balloon은 가장 작은 값이다. 

right에서 이 값을 빼준다(최후까지 남을 수 있는 풍선임).

balloon이 -92, right[0][NUM]이 -92로 같을 때 right에서 -92를 pop했다. -92는 -71과 -16과 비교하는데 balloon(-91)이 더 크지 않으므로 result-=1실행 안함.

-71도 right에서 pop함. right에서 -68과 left에서 -92와 비교해서 result-=1 안함.

-68도 right에서 pop함. right에서 -61과 left에서 -92와 비교해서 result-=1 안함.

-61도 pop함. right에서 -33과 left에서 -92와 비교해서 result-=1 안함

반복문이 끝난 후 right를 조회하면 최후까지 남을 수 없는 풍선들이 남는 것을 알 수 있다(마지막 값인 -33은 반복문에서 안 돌렸으니 제외).

 

 

 

import math
def solution(a):
    answer=0
    left, right =math.inf, math.inf
    maps=[[0 for _ in range(len(a))] for _ in range(2)]		# a의 길이만큼 left와 right 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]:	# a[i]가 양옆 값보다 작거나 같다면 살아남음
            answer+=1

    return answer

1. 맨 앞과 맨 뒤는 무조건 남는다.

맨 앞 값과 맨 뒤 값은 inf랑 비교하게 되므로

2. 가운데 값은 양옆 값보다 작다면 살아남는다.

 

left와 right에 큰 수 inf를 넣는다.

maps에 a의 길이만큼 0으로 초기화된 리스트 2개(left, right)를 만든다. 

반복문으로 letf와 right에 작은 값을 넣고 maps에 추가.

 

 

# https://velog.io/@eehwan/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%92%8D%EC%84%A0-%ED%84%B0%ED%8A%B8%EB%A6%AC%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC
def solution(a) :
    result=[False for _ in range(len(a))]
    minFront, minRear=float("inf"), float("inf")
    for i in range(len(a)) :
        if a[i] < minFront :
            minFront=a[i]
            result[i]=True
        if a[-1-i] < minRear :
            minRear=a[-1-i]
            result[-1-i]=True
    return sum(result)

왼쪽 또는 오른쪽에 자기 자신보다 더 큰 값만 있어야 터트릴 수 있다

 

 

# https://dev-note-97.tistory.com/165
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

양방향으로 최솟값을 memoization

ex) 테케 2

[-16,27,65,-2,58,-92,-71,-68,-61,-33]

<- 방향

[-92, -92, -92, -92, -92, -92, -71, -68, -61, -33]

-> 방향

[-16, -16, -16, -16, -16, -92, -92, -92, -92, -92]

 

 

 

문제 출처 👉 프로그래머스