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

문제 링크:

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

회고:

• 중요 포인트:
  • 인접한 두 풍선 중 번호가 작은 풍선을 터뜨리는 행위는 최대 한 번만 허용된다. (즉, 번호가 큰 걸 남길 수 있는 기회는 최대 1번)
  • 풍선에 적힌 숫자는 모두 다르다. (겹치는 숫자 없음)
• 왼쪽에서 오른쪽으로 스캔:
  각 풍선 위치에서 자신보다 왼쪽에 있는 풍선들 중 가장 작은 값을 기록한다. (left_min_value_list)
• 오른쪽에서 왼쪽으로 스캔:
  각 풍선 위치에서 자신보다 오른쪽에 있는 풍선들 중 가장 작은 값을 기록한다. (right_min_value_list)
• 최종 확인:
  • 각 풍선 위치에서 해당 풍선이 최종적으로 남을 수 있는지를 확인한다.
  • (자신보다 왼쪽에 있는 풍선들 중 가장 작은 값, 자기 자신, 자신보다 오른쪽에 있는 풍선들 중 가장 작은 값) 이렇게 3개의 값을 두고 자기 자신이 최종적으로 남을 수 있는지를 보는 것이다.
  • 왼쪽에 있는 풍선들 중 최솟값, 오른쪽에 있는 풍선들 중 최솟값을 두고 비교했을 때, 자기자신보다 큰 값이 적어도 하나라도 있다면 자기자신은 최종적으로 남을 수 있는 값이다.

python

def solution(a):
    if len(a) in (1, 2):
        return len(a)

    # 양쪽 끝에 있는 숫자는 최후까지 남기는 것이 가능
    count = 2

    # 왼쪽 부터 순차적으로 최솟값 구하기
    left_min_value = a[0]
    left_min_value_list = [0]  # 0번째 인덱스 값과 마지막 인덱스 값은 어차피 비교대상이 아니므로 어떤 숫자가 들어가더라도 상관 없음
    for i in a[1:]:
        left_min_value_list.append(left_min_value)
        left_min_value = min(left_min_value, i)

    # 오른쪽 부터 순차적으로 최솟값 구하기
    right_min_value = a[-1]
    right_min_value_list = [0]  # 0번째 인덱스 값과 마지막 인덱스 값은 어차피 비교대상이 아니므로 어떤 숫자가 들어가더라도 상관 없음
    for i in a[-1::-1]:
        right_min_value_list.append(right_min_value)
        right_min_value = min(right_min_value, i)

    right_min_value_list = right_min_value_list[::-1]

    # 최후까지 남기는 것이 가능한 풍선 개수 구하기
    for idx in range(1, len(a) - 1):
        if a[idx] < left_min_value_list[idx] or a[idx] < right_min_value_list[idx]:
            count += 1

    return count


if __name__ == "__main__":
    result = solution([-16, 27, 65, -2, 58, -92, -71, -68, -61, -33])
    print(result)

6