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

 

그리디로 풀었을 때,

정확성 테스트

테스트 1 〉	통과 (0.01ms, 10.4MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (20.87ms, 10.2MB)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	실패 (시간 초과)

채점 결과

정확성: 20.0

합계: 20.0 / 100.0

 

DP로 풀었을 때

def solution(a):
    answer = 2
    L = len(a)
    dp_left, dp_right= [a[0]]*L, [a[-1]]*L
    for i in range(1, L) :
        dp_left[i] = min(dp_left[i-1], a[i])
    for i in range(L-2,0,-1) :
        dp_right[i] = min(dp_right[i+1],a[i])
    
    for i in range(1,L-1) :
        if a[i] > max(dp_left[i-1], dp_right[i+1]) : continue
        else : answer += 1
    return answer

정확성 테스트

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (1.15ms, 10.3MB)
테스트 4 〉	통과 (60.31ms, 15.2MB)
테스트 5 〉	통과 (337.91ms, 36.9MB)
테스트 6 〉	통과 (505.87ms, 50.4MB)
테스트 7 〉	통과 (670.73ms, 63.9MB)
테스트 8 〉	통과 (674.25ms, 63.8MB)
테스트 9 〉	통과 (673.91ms, 63.8MB)
테스트 10 〉	통과 (616.73ms, 64MB)
테스트 11 〉	통과 (678.17ms, 63.8MB)
테스트 12 〉	통과 (683.53ms, 63.9MB)
테스트 13 〉	통과 (687.51ms, 63.9MB)
테스트 14 〉	통과 (697.65ms, 63.8MB)
테스트 15 〉	통과 (687.43ms, 63.9MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0