[Programmers] Lv2 - 디펜스 게임

문제

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

프로그래머스

 

풀이

힙을 사용하는 문제다.

import heapq


def solution(n: int, k: int, enemy: list) -> int:
    """
    round: 통과한 라운드의 수
    enemies: 현재까지 상대한 적의 수
    """
    round = enemies = 0
    heap = []

    for e in enemy:
        heapq.heappush(heap, -e)
        enemies += e

        if enemies > n:
            if not k:
                break
            k -= 1
            enemies += heapq.heappop(heap)
        round += 1
    return round

다른 풀이와 별 다를바 없기에 설명은 생략한다.

 

풀이 과정:

1. heapq 모듈을 import한다.

2. 통과한 라운드의 수를 담을 round, 현재까지 병사들로 상대한 적의 수 enemies를 0으로 초기화한다.

(근데 쓰면서 알아차린건데 변수명으로 round는 적절하지 않다... 기존에 있는 함수명과 겹침)

3. 각 라운드별 적의 수가 담겨있는 enemy를 순회하며 heap에 push한다.

    3.1. 파이썬의 heapq은 기본적으로 최소힙이기 때문에 -를 붙여 음수로 집어넣는다.
    3.2. 적의 수 e를 enemies에 더한다.

4. 만약 enemies가 n보다 커질 경우,

    4.1. 무적권 k가 존재하지 않는다면 break
    4.2. 존재한다면 k를 1 차감하고 heap에서 가장 작은 값(-를 붙였으므로 실질적으로는 가장 큰 적의 수가 된다)을 pop한뒤, enemies에 더해준다. 즉, 여태까지 상대한 적의 수 중 가장 많은 적의 수를 pop한뒤 enemies에서 차감한다. (무적권으로 상대했으므로 사실상 상대하지 않은 셈이다.)

5. 한번 순회할때마다 round를 1 증가시킨다.

6. round 반환.

---

힙(heap)이란?

: 최댓값/최솟값을 빠르게 찾을 수 있도록 만들어진 완전이진트리 형식의 자료구조.

 

최대힙(Max Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같음

최소힙(Min Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같음

 

특징

• 완전 이진 트리 구조
• 루트 노드는 항상 최솟값(최소힙) 또는 최댓값(최대힙)을 가짐
• 배열을 사용하여 구현. 배열의 첫번째 요소(인덱스 0)은 사용하지 않거나 루트 노드로 사용함
• 부모 노드와 자식 노드와의 관계
  • 부모 노드의 인덱스를 i라고 할 때, 왼쪽 자식 노드의 인덱스는 2i, 오른쪽 자식 노드의 인덱스는 2i+1
  • 자식 노드의 인덱스를 j라고 할 때, 부모 노드의 인덱스는 j//2

 

Python에서의 힙 사용

파이썬은 heapq모듈을 사용하여 쉽게 구현할 수 있다. 기본적으로 최소힙이다.

 

주요 메서드

• heapq.heappush(heap, item): item을 힙에 삽입
• heapq.heappop(heap): 힙에서 최솟값을 제거하고 반환
• heapq.heapify(x): 리스트 x를 힙으로 변환
• heapq.nlargest(n, iterable): iterable에서 가장 큰 n개의 요소를 반환
• heapq.nsmallest(n, iterable): iterable에서 가장 작은 n개의 요소를 반환

 

사용 예시

import heapq


# 빈 힙 생성
heap = []

# 힙에 요소 삽입
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print(heap)  # [1, 3, 7, 4]

# 힙에서 최솟값 제거 및 반환
min_value = heapq.heappop(heap)
print(min_value)  # 1
print(heap)  # [3, 4, 7]

# 리스트를 힙으로 변환
list1 = [5, 2, 9, 1, 7]
heapq.heapify(list1)
print(list1)  # [1, 2, 9, 5, 7]

# 최댓값 및 최솟값 찾기
list2 = [4, 2, 9, 7, 5]
largest_three = heapq.nlargest(3, list2)
smallest_two = heapq.nsmallest(2, list2)
print(largest_three)  # [9, 7, 5]
print(smallest_two)  # [2, 4]

 

최대힙 구현하기

말했다시피 기본적으로 최소힙으로 동작하기 때문에, 약간의 변형을 거쳐야한다.

바로 힙에 요소를 삽입할 때 음수를 붙이는것이다. 이렇게하면 가장 작은 요소가 실질적으로는 가장 큰 요소가 되는 셈.

(sort 사용 시 key의 기준이 여러개일때. 오름차순/내림차순 둘 다 고려해야할때를 생각하자.)

import heapq


# 빈 힙 생성
max_heap = []

# 최대 힙에 요소 삽입
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -7)
heapq.heappush(max_heap, -3)

print(max_heap)  # [-7, -3, -1, -4]

# 최대 힙에서 최댓값 제거 및 반환
max_value = -heapq.heappop(max_heap)
print(max_value)  # 7
print(max_heap)  # [-4, -3, -1]