프로그래머스 3단계 - [풍선 터트리기]

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

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

1. 문제이해

 - 주어진 리스트에서 인접한 두 수 를 골라 큰 수를 제거한다.

 - 단 한번에 한해서 작은 수를 제거할 수 있다.

 

2. 코드 작성

def solution(a):
    
    if len(a) <= 3:
        return len(a)

    left_arr = a[:a.index(min(a))]
    right_arr = a[a.index(min(a))+1:]
    right_arr = right_arr[::-1]
    
    answer = 1
    temp = 0
    
    for idx, value in enumerate(left_arr):
        if idx == 0:
            temp = left_arr[idx]
            answer += 1
        else:
            if temp > left_arr[idx]:
                answer += 1
                temp = left_arr[idx]

    for idx, value in enumerate(right_arr):
        if idx == 0:
            temp = right_arr[idx]
            answer += 1
        else:
            if temp > right_arr[idx]:
                answer += 1
                temp = right_arr[idx]
    
    return answer

 

3. 풀이간 체크사항

 1) 우선 가장 작은 수와 양 끝에 있는 값은 무조건 포함된다. 

  - A B C D E F 0 G => 0이 제일 작은 수라 하자

  - (A (B (C (D (E (F (0 G))))))) 이런식으로 양 끝은 무조건 포함될 수 있다.

 2) 만약 양 끝보다 가까운 값이 양 끝값보다 작으면 해당 값도 가능하다.

 3) 위 두가지를 기준으로 예외처리 해 가면서 로직 구현