풍선 터트리기 (스택, 최솟값 비교, memoization)

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

프로그래머스

 

분석

• 배열의 양쪽의 최솟값 중 하나라도 자신보다 클 경우 끝까지 남을 수 있음
• 배열 인덱스 값마다 최솟값을 일일히 계산하면 시간초과

 

풀이

1. stack

Time: 135.97 ms

def solution(a):
    stack = []
    for x in a:
        if len(stack) < 2:
            stack.append(x)
        else:
            while(len(stack) >= 2 and stack[-2] < stack[-1] > x):
                stack.pop(-1)
            stack.append(x)

    return len(stack)

 

2.  최솟값 비교

Time: 328.18 ms

def solution(a):
    answer = 1
    M = min(a)
    for _ in range(2):
        m = a[0]
        i = 1
        while m != M:
            if m >= a[i]:
                m = a[i]
                answer += 1
            i += 1
        a.reverse()
    return answer

 

3. 최솟값 memoization

Time: 642.23 ms

#  양쪽의 최솟값 중 하나라도 자신보다 클 경우 끝까지 남을 수 있음

def solution(a):
    if len(a)==1: return 1

    answer=2 # 양쪽 끝
    
    n=len(a)
    
    lm=[a[0]]
    rm=[a[-1]]

    for i in range(1, n):
        # 왼쪽 최솟값 저장
        if a[i]<lm[-1]:
            lm.append(a[i]) # 최솟값 추가
        else:
            lm.append(lm[-1]) # 기존값 추가
            
        # 오른쪽 최솟값 저장
        if a[-1-i]<rm[-1]: 
            rm.append(a[-1-i]) # 최솟값 추가
        else:
            rm.append(rm[-1])  # 기존값 추가
    rm.reverse()
          
    for i in range(1, n-1):
        if lm[i-1]>a[i] or rm[i+1]>a[i]:
            answer+=1
        
    return answer

https://dev-note-97.tistory.com/165

[프로그래머스] 풍선 터뜨리기 / Python

 

 

 

월간코드챌린지