[파이썬] 풍선 터트리기

문제 설명

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

프로그래머스

문제 풀이

• 규칙에 따라 최종적으로 남을 수 있는 1개의 풍선은 몇 개 가능한 지 출력하는 문제

• 인접한 두 풍선을 고른 뒤, 하나를 터트림
• 번호가 작은 풍선을 1번만 터트리기 가능
• 이후에는 큰 풍선만 터트림

• cur 기준으로 왼쪽에서의 최솟값과 오른쪽에서의 최솟값을 구함
  • 배열의 길이가 1백만이므로 n^2으로 구할 시 시간 초과가 뜸
  • 오른쪽에서의 최솟값은 반대 방향으로 일직선 탐색
• cur 기준 구한 양쪽의 최솟값을 통해
  • 왼쪽 최솟값이 cur보다 크다면 그냥 성공 ( 오른쪽에서 어떤 값이 나오더라도 1번만 터트릴 수 있으니까)
  • 왼쪽 최솟값이 cur보다 작다면 cur이 살아남기 위해서는 오른쪽 최솟값보다는 작아야함 ( 왼쪽에서 이미 작은 거 터트릴 기회 1번 썼으니까)
    • 오른쪽 최솟값이 cur 보다 크다면 answer 는 + 1 ( 크니까 자동으로 터트릴 수 있어서 cur은 살아남음)
    • 오른쪽 최솟값이 cur보다 작다면 continue 

 

소스 코드

def solution(a):
    answer = 2	# a[0]과 a[-1] 은 어떠 한 경우라도 살아남기 가능함
    n = len(a)
    min_arr = [0]*n	#오른쪽 최솟값
    min_arr[0]=a[0]
    min_arr[-1]=a[-1]
    arr = [a[0]]*n	#왼쪽 최솟값
    
    for i in range(-2,-n,-1):
        if a[i]>min_arr[i+1]:
            min_arr[i]=min_arr[i+1]
        else:
            min_arr[i]=a[i]
    for i in range(1,n):
        if a[i] < arr[i-1]:
            arr[i]=a[i]
        else:
            arr[i]=arr[i-1]

    for i in range(1,n-1):
        if a[i]<arr[i-1]:
            answer+=1
        else:
            if a[i]>min_arr[i+1]:
                continue
            else:
                answer+=1

    return answer

print(solution([-16,27,65,-2,58,-92,-71,-68,-61,-33]))