[프로그래머스 / 파이썬 ] 풍선 터트리기

🔗 Link 

https://school.programmers.co.kr/learn/courses/30/lessons/68646

프로그래머스

 

🧩 Source Code

def solution(a):
    answer = len(a)
    left_min = []
    mini = float('inf')
    for i in a:
        mini = min(mini, i)
        left_min.append(mini)
    
    mini = float('inf')
    right_min = []
    for i in range(len(a)-1,-1,-1):
        mini = min(mini, a[i])
        right_min.append(mini)
    right_min = right_min[::-1]
    
    for i in range (len(a)):
        if (a[i] > left_min[i] and a[i] > right_min[i]) : answer -= 1        
    
    return answer

---

 

📝 Commentary

우선 가장 고려했던 것은 시간 복잡도였다.

 

제한 사항

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

이러한 제한 사항을 가지고 있기 때문에 a를 n**2번 순회하면 안됐고, logn 연산도 애매했다.

 

그래서 for문을 1번씩 여러번 사전에 세팅을 해놓고 하는 방법을 생각했다.

 

로직

어떤 숫자를 기준으로 양 옆에 자기보다 작은 수가 있으면 안된다는 것 << 이것이 문제 해결 포인트다.

한번은 자기보다 작은 애를 터트릴 수 있다는 점에 주목했다.

 

예를 들어 자기 기준으로 오른쪽에 가장 작은 수가 있으면

그 숫자보다 큰애는 다 터트리고 마지막에 그 가장 작은 수를 터트리면 어떤 경우에서든 자기보다 오른쪽에는 다 터트릴 수 있는 경우다.

하지만 이러면 왼쪽에 자기보다 작은 숫자가 있는 경우 못 터트리기 때문에

 

자기 기준으로 왼쪽, 오른쪽에 자기보다 작은 숫자가 없어야 한다는 것이다.

원래 배열

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

자기 왼쪽을 봤을 때 작은 가장 숫자
[-16,-16,-16,-16,-16,-92,-92,-92,-92,-92]

자기 오른쪽을 봤을 때 가장 작은 숫자
[-92,-92,-92,-92,-92,-92,-71,-68,-61,-33]

 

for i in range (len(a)):
    if (a[i] > left_min[i] and a[i] > right_min[i]) : answer -= 1

 

하면 이렇게 최종적으로 자기 보다 작은숫자가 있었냐를 보고 해당하면 답에서 뺴주면 된다.

---

ps. 생각해보니 왼쪽 오른쪽 세팅할때 한번에 for문으로 처리해도 됐을 것 같다.

그럼 이렇게 됐겠지?

def solution(a):
    answer = len(a)
    left_min, right_min = [], []
    mini_l, mini_r = float('inf'), float('inf')
    
    for i in range(len(a)-1,-1,-1):
        mini_l = min(mini_l, a[len(a) -1 - i])
        left_min.append(mini_l)
        mini_r = min(mini_r, a[i])
        right_min.append(mini_r)
    right_min = right_min[::-1]
    
    for i in range (len(a)):
        if (a[i] > left_min[i] and a[i] > right_min[i]) : answer -= 1        
    
    return answer