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

😎코딩테스트 연습>월간 코드 챌린지 시즌1>풍선 터트리기

📘 문제풀이

min 값의 인덱스를 중심으로 양끝에서 더 작은 수라면 최소값을 바꿔준다. 최소값이 바뀐다는 것은 자신의 왼쪽이나 오른쪽에 있는 값을 터트릴 수 있다는 것이기 때문에 살아남을 수 있다. min 값을 가진 풍선은 무조건 살아남는다. 만약 살아남아야하는 풍선이 min값이 아니라면 자신보다 작은 수를 터트리는 기회는 무조건 min값에 한번 사용한다.

def solution(a):
    answer = 0
    x = a.index(min(a))
    
    
    ml = a[0]
    for i in range(x):
        if ml > a[i]:
            ml = a[i]
            answer += 1
    
    mr = a[-1]
    for i in range(len(a)-1, x, -1):
        if mr > a[i]:
            mr = a[i]
            answer += 1
    
    if x != 0  and x != len(a)-1:
        answer += 1
    
    answer += 2
    return answer

---

문제해결 방법은 알았지만 시간초과를 해결하는데 오래걸렸다.

시간초과1

def solution(a):
    answer = 0
    for i in range(len(a)):
        if i == 0 or i == len(a)-1:
            answer += 1
        else:
            if min(a[:i]) > a[i] or min(a[-(len(a)-i-1):]) > a[i]:                
                answer += 1
            
            
    return answer

시간초과2

def solution(a):
    answer = 0
    for i in range(len(a)):
        if i == 0 or i == len(a)-1:
            answer += 1
        else:
            m1 = a[i]
            for n in range(i):
                if m1 > a[n]:
                    m1 = a[n]
            m2 = a[i]
            for n in range(i+1, len(a)):
                if m2 > a[n]:
                    m2 = a[n]
            if m1 == a[i] or m2 == a[i]:
                
                answer += 1
            
            
    return answer

시간초과3

def solution(a):
    answer = 0
    x = a.index(min(a))
    for i in range(len(a)):
        if i == 0 or i == len(a)-1 or i == x:
            answer += 1
        elif i > x:
            flag = 0
            for n in range(i+1, len(a)):
                if a[n] < a[i]:
                    flag = 1
            if flag == 0:
                answer += 1
        else:
            flag = 0
            for n in range(i):
                if a[n] < a[i]:
                    flag = 1
            if flag == 0:
                answer += 1
        
            
    return answer