[프로그래머스] 디펜스 게임 (Lv 2)

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

프로그래머스

 

쉽게 아이디어도 보이지 않았고, 하도 heap을 안 쓰다 보니 고전한 문제.

자료구조로서 heap의 역할은 최대/최소값을 빠르게 찾아주는 역할임을 잊지 말자.

아이디어는 그리디이다. 만일 진행하다가, 막힐 경우 그전까지 가장 쎈 스테이지에다가 스킵을 투척해버린다.
막힐 경우 바로 이를 시행하기 때문에, 던지고도 또 막힐 일은 없다.

아, 적군의 합도 갱신해줘야 하는데 list 합 돌리면 늦어진다. 따라서 합은 따로 그때그때 계산해줘야 한다.

힙의 최댓값 찾는 과정  = 삭제로 시간 복잡도 O(log N), enemy를 도는 과정으로 O(N)
O(NlogN)으로 풀리는 문제이다.

 

# 최댓값 / 최소값을 찾아주는 heap을 잊지 말자.
# 파이썬에서는 기본적으로 최솟값을 찾아준다.
# 따라서, 최대를 위해서는 -를 붙인다.
# 절대 잊지 말자!!!! 중요하다!

import heapq
def solution(n, k, enemy):
    answer = 0
    enemy_list = []
    heapq.heapify(enemy_list)
    enemy_sum = 0
    i = 0
    while i < len(enemy):
        enemy_sum += enemy[i]
        heapq.heappush(enemy_list, (-enemy[i], enemy[i]))
        if enemy_sum > n and k > 0:
            enemy_sum -= enemy_list[0][1]
            heapq.heappop(enemy_list)
            k -= 1
        elif enemy_sum > n and k == 0:
            break      
        i += 1
    return i