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

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

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

 

처음에는 이걸 어쩌라는거야.. 싶었다😂

그래서 일단 한번 검색해서 접근법을 알아낸 후 계산해봤다...!!!

 

접근법은 지금 숫자를 기준으로, 왼쪽/오른쪽에서 최솟값을 확인하여 비교하는 방법이다.

 

입출력예제 2를 보면 표처럼 정리 할 수 있다!

왼쪽, 오른쪽의 최소값을 저장할 small_nums 라는 배열을 생성한 다음 for문을 돌면서 하나씩 넣어준 것이다.

 

58과 -68을 예로 들어 설명하면...

58을 기준으로 왼쪽(-16, 27, 65, -2) 에서 최소값은 -16이고,
오른쪽(-92, -71, -68, -61, -33)에서 최소값은 -92이다!

-68을 기준으로 왼쪽(-16, 27, 65, -2, 58, -92, -71) 에서 최소값은 -92이고,
오른쪽 (-61, -33) 은 둘 다 -68보다 크므로, 최소값을 -68로 변경한 후 저장한다!

 

🙋‍♀️ 작성한 코드

def solution(a):
    answer = 0
    small_nums= [[0, 0] for _ in range(len(a))]

    INF = int(10e9)
    left = INF
    right = INF
    
    #왼쪽 확인
    for i in range(len(a)):
        if left > a[i]:
            left = a[i]
        small_nums[i][0] = left
    
    #오른쪽 확인
    for i in range(len(a)-1, -1, -1): #맨 오른쪽에서부터 <- 이쪽 방향으로 와야 하므로
        if right > a[i]:
            right = a[i]
        small_nums[i][1] = right
    
    for i in range(len(a)):
        if a[i] <= small_nums[i][0] or a[i] <= small_nums[i][1]:
            answer += 1
    print(small_nums)
    
    return answer