99클럽 코테 스터디 38일차 TIL + 그리디(Greedy)

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "디펜스 게임" 문제를 풀었다.
- 오늘 주제는 오랜만에 그리디(Greedy)다.

[나의 코드]

import heapq

def solution(n, k, enemy):
    heap = []
    
    for i in range(len(enemy)):
        heapq.heappush(heap, enemy[i])
        
        if len(heap) > k:
            n -= heapq.heappop(heap)
        
        if n < 0:
            return i
    
    return len(enemy)

동네 사람들, 제한 사항 좀 보세요. 아주 숫자가 미쳐 돌아가는 것이 보일 것이다.
1 ≤ n ≤ 1,000,000,000
1 ≤ k ≤ 500,000
1 ≤ enemy ≤ 1,000,000

그러니 당연히 '시간복잡도가 터질 수 있겠다~'를 생각하게 된다.

그다음에 이 문제가 그리디라고 하니까 효율적인 방안이 있다는 것이다. 대충 다들 아래처럼 생각하지 않았을까 싶다.
① 무적권을 효율적으로 사용하기 위해서는 n으로 막을 수 없는 큰 적군을 먼저 무적권으로 처리해야 한다.
② 현재까지 만난 가장 큰 적군을 추적하고, 무적권이 부족할 때 큰 적군을 우선적으로 무적권으로 대체한다.

→ 그러니까 우선적으로 무언갈 처리할 수 있는 힙을 쓰면 좋을 것으로 판단된다.

무적권의 수보다 더 많은 적군이 등장했을 때, 가장 큰 적군부터 무적권을 사용하는 방식이다.
n이 0보다 작아지면 더 이상 적군을 막을 수 없으므로 종료하고 현재까지 막은 적군의 수를 반환한다.

원래 이 코드 말고 최대힙 코드로 짰는데, 이게 더 보기 좋아서 이걸로 바꿔 풀었다. 그렇다.

[오늘의 회고]
- 으아아앙아 그리디는 너무 싫다. 그리디 저리 가.
- 지금 감상에 젖어 있으니까 빨리 가야겠다. 끝!