[programmers] Lv3 풍선 터트리기 - Python

코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

 

<문제 풀이>

  처음에는 그냥 생각나는 대로 다 해본 것 같다. 하지만 시간이 오래 걸리고 아이디어가 떠오르지 않아 접근법 힌트를 보고 풀게 되었다. 좌 -> 우 방향으로 최솟값을 갱신해 가며 answer에는 갱신되는 지점의 값을 추가한다. 마찬가지로 우 -> 좌 방향으로 최솟값을 갱신해 가며 answer에 갱신되는 지점의 값을 추가한다. set을 통해 중복된 지점을 제거한 후 개수를 return 한다.

 

 

 

<Code>

def solution(a):
    answer = set()    # 중복 값 배제를 위한 set
    n = len(a)
    left, right = 1000000001, 1000000001    # 각 방향 최솟값 갱신을 위한 초기값

    for i in range(n):
        if a[i] < left:    # 좌측 기준으로 최솟값 찾으면서 갱신
            left = a[i]
            answer.add(i)

        if a[n-1-i] < right:    # 우측 기준으로 최솟값 찾으면서 갱신
            right = a[n-1-i]
            answer.add(n-1-i)

    return len(answer)

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.