99클럽 코테 스터디 9일차 TIL + 힙(Heap)

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "더 맵게" 문제를 풀었다.
- 힙 자료구조를 이용하여 푸는 문제였다.
- 기본적으로 파이썬으로 힙 자료구조를 구현할 줄 알아야 한다. 근데 나는 이미 알고 있어서 수고를 덜었다. (어쩔)

[나의 코드]

import heapq

def solution(scoville, K):
    answer = 0
    q = []
    
    # heapq.heapify(scoville) 
    # 이렇게 쓸 수도 있다. 시험장에선 기억이 안 날지도 모르니... 풀어썼다.
    for num in scoville:
        heapq.heappush(q, num)
    
    while q[0] < K:
        quotient = heapq.heappop(q) + (heapq.heappop(q) * 2)
        heapq.heappush(q, quotient)
        answer += 1
        
        if q[0] < K and len(q) == 1:
            return -1
    return answer

문제를 읽자마자 다음 로직을 짜 보았다.
① 힙을 하나 만든다.
② 으뜸값과 버금값을 이용하여 주어진 식에 대입해 계산한다.
③ 다시 힙에 계산한 값을 넣어주고, 횟수를 세준다.

종료 조건을 이해하기 위해선 힙 자료구조를 알아야 한다.
기본적으로 힙은 최소 힙이 기본 설정값이다. 그래서 맨 앞 원소가 늘 가장 작은 값이 온다.
가장 작은 값이 K보다 크면 아무 소용이 없으니 종료 조건은 저러하다.

그리고 pop 연산을 두 번하기 때문에 힙의 길이가 1이면 오류가 날 것이다.
그래서 힙의 길이가 1이고 첫 원소의 값이 K보다 작다면 -1을 반환한다.

[오늘의 회고]
- 참고로 힙 자료구조 삽입/삭제의 시간 복잡도는 O(㏒n)이다.
- 구현 자체는 까다롭지 않은 문제였던 것 같다.
- 뭐... 더 말할 게 있는가? 아 요즘 올림픽 재밌다. 끝!