[programmers] lv.2 디펜스 게임

문제 바로가기

문제 접근

while로 접근 : 당연히 시간초과
heap 자료구조로 접근 (heap은 그 최솟값을 추출하기 용이)

heap 시간초과 : list로 되어있는 값의 sum, len을 이용해서 그 때 그 때 비교했는데 이 부분에서 시간이 미세하게 더 걸려서 초과 > 최대한 상수로 정의해서 풀이하기

정답 코드

import heapq
def solution(n, k, enemy):
    num_enemy = []
    answer = 0 # 현재 라운드
    sum_enemy = 0
    for i in enemy:
        heapq.heappush(num_enemy,-i) # 최솟값 추출하므로 음수로 대입
        sum_enemy += i
        if sum_enemy > n:
            if k == 0:
                break
            else:
                sum_enemy += heapq.heappop(num_enemy) # 최솟값 추출
                k -= 1 # 무적권 사용
        answer += 1
    return answer

자료구조 힙(heap)

• 우선 순위에 따라 데이터를 접근할 수 있는 자료구조로 최솟값, 최댓값에 빠르게 접근할 경우에 많이 사용됨, 시간복잡도 O(logn)
• 일종의 완전 이진트리를 기반으로 MinHeap, MaxHeap으로 구성된다.

import heapq
heap = [] # 를 이용해서 일반적으로 최소 힙으로 변환해서 사용

• heapq 관련 함수

  heapify(iterable) : 주어진 iterable을 힙으로 변환
  heappush(heap, item) : heap에 i요소 삽입
  heappop(heap) : healp에서 가장 작은 원소를 제거하고 반환
  heappushpop(heap, item) : item을 heap에 삽입하고 가장 작은 원소를 제거하고 반환 (heappush > heappop)
  heapreaplce(heap, item) : heap에서 가장 작은 원소를 제거한 후 item을 삽입 (heappop > heappush)

• 기본적으로 min heap을 사용하기 때문에 최댓값을 반환할 경우에는 item에 -을 붙여서 음수를 기준으로 사용한다.