Level 3 풍선 터트리기 Python 3

https://programmers.co.kr/learn/courses/30/lessons/68646?language=python3 

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

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_풍선터트리기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(a):
    min_left, min_right = 1000000001, 1000000001
    check = [0]*len(a)
    for i in range(len(a)):
        if a[i] < min_left:
            min_left = a[i]
            check[i] = 1
        if a[-1-i] < min_right:
            min_right = a[-1-i]
            check[-1-i] = 1
    
    return sum(check)

---

풀이 과정

1 <= len(a) <= 1,000,000이기 때문에 모든 경우에 대해서 풍선을 터트리는 시뮬레이션을 돌리면 시간 초과가 난다.

남길 풍선을 기준으로 왼쪽 방향에 있는 풍선들 중 가장 작은 값과 오른쪽 방향에 있는 풍선들 중 가장 작은 값을 비교해준다.

둘 중 한 방향에 남기려고 하는 풍선의 숫자가 더 작다면 해당 풍선을 터트리지 않고 남길 수 있다.

def solution(a):
	#초기값 설정
    min_left, min_right = 1000000001, 1000000001
    
    #풍선 체크
    #check[i] = 1 -> i번째 풍선을 터트리지 않고 남길 수 있다
    check = [0]*len(a)
    
    for i in range(len(a)):
    	#i번째 풍선이 왼쪽에 있는 풍선들 중 가장 작은 값인 경우, i번째 풍선을 터트리지 않고 남길 수 있다
        if a[i] < min_left:
        	#min_left 갱신
            min_left = a[i]
            check[i] = 1
            
        #뒤에서 i번째 풍선이 오른쪽에 있는 풍선들 중 가장 작은 값인 경우, 뒤에서 i번째의 풍선을 터트리지 않고 남길 수 있다
        if a[-1-i] < min_right:
            min_right = a[-1-i]
            check[-1-i] = 1
    
    #터트리지 않고 남길 수 있는 풍선의 개수 return
    return sum(check)
    
#시간복잡도 = O(n), 공간복잡도 = O(n)