[프로그래머스][level3] 풍선 터트리기 - python

문제 링크 

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

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

 

문제 풀이 - 다른 블로그 참고 

자신 기준 왼쪽/ 오른쪽 리스트의 최솟값 둘 중 하나 이상보다 작을 경우 살아남을 수 있다. 

- 왼쪽/ 오른쪽 리스트의 최솟값보다 클 경우 : 작은 숫자 한번 터트려도 두개의 숫자가 남게 되므로, 하나만 남길 수 없다. 

- 왼쪽 리스트의 최솟값보다 작거나, 오른쪽 리스트의 최솟값보다 작을 경우 (하나의 최솟값보단 크고, 하나의 최솟값보단 작을 경우) : 큰 숫자를 터트리고, 작은 숫자 한 번 터트리면 하나만 남길 수 있다. 

- 왼쪽/ 오른쪽 리스트의 최솟값보다 작을 경우 : 큰 숫자들만 터트려도 하나만 남게 된다. 

INF = int(1e9)

def solution(a):
  answer = 0 
  left , right = INF, INF

  # 각 숫자별 본인 왼쪽에 본인보다 제일 작은 수 
  # 각 숫자별 본인 오른쪽에 본인보다 제일 작은수 
  maps = [[ 0 for _ in range(len(a))] for _ in range(2)]

  # i 인덱스 왼쪽에 a[i]보다 가장 작은 수 
  for i in range(len(a)):
    if left > a[i]:
      left = a[i]

    maps[0][i] = left 
  
  # i 인덱스 오른쪽에 a[i]보다 가장 작은 수 
  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)):
    # a[i] 기준 오른쪽이나 왼쪽의 최솟값보다 작거나 같을 경우 (가장 작은 수가 본인일 수도 있음)
    if a[i] <= maps[0][i] or a[i] <= maps[1][i]:
      answer += 1 

  return answer