(프로그래머스, 파이썬) 힙 - [더 맵게, 디스크 컨트롤러, 이중우선순위큐]

예전에 힙 관련해서 풀고 나서 다시 보니까 느낌이 새로웠다.

역시 공부는 지속적으로 해야하는 것..

친구가 '힙 보이'라고 했던게 생각났다..

---

문제 링크

<더 맵게>

문제의 조건은 다음과 같다.

 

모든 scoville의 값들이 K를 넘을 때 까지 '가장 작은 값, 두 번째로 작은 값'을 각각 빼서(pop) 곱해서 더하고 넣어라(push)

단, 모든 스코빌 값들이 K 이상의 값을 가질 수 없다면 -1을 리턴해야 한다.

import heapq as h

def solution(scoville, K):
    h.heapify(scoville) #힙으로 만들어준다.
    count_mix = 0

    while scoville[0] < K: #오름차순 정렬이므로 첫 원소가 K보다 크거나 같을 때까지 반복한다.
        if len(scoville) == 1: #한 개 남은 원소가 K보다 작다면 만들 수가 없는 상황이 된 것.
            return -1
        min_scoville = h.heappop(scoville) #가장 적은 스코빌
        sec_scoville = h.heappop(scoville) #두번째로 적은 스코빌
        new_scoville = min_scoville + sec_scoville * 2 #섞는다
        h.heappush(scoville, new_scoville) #힙에 넣고
        count_mix += 1 #횟수를 센다
    
    return count_mix

while 분기를 생각해내는 것이 포인트였던 문제 같다.

파이썬의 경우 heap이 기본적으로 최소 힙이기 때문에, 바로 pop을 하게 되면 최소값부터 pop하게 된다.

---

<디스크 컨트롤러>

문제를 이해하는 데에 시간이 좀 필요했다.

즉, 각 작업별로 (시작할 수 있는 시간, 작업 시간)이 주어지고, 모든 작업들을 다 끝냈을 때,

그 각 작업의 (시작할 수 있었던 시간 ~ 종료된 시간)을 다 더해서, 작업의 수로 평균을 냈을 때 가장 작게 만들어줘야 한다는 것이다.

파이썬이 최소 힙인 성질을 이용해서 풀 수 있다.

#실행할 수 있는 상황에서 가장 짧은 것부터 실행한다 / 이외에는 먼저 요청이 들어온 작업을 수행한다.
#하위 노드 두개 중, time이 가장 짧은 것을 우선순위로 두어야 한다.

import heapq as h

def solution(jobs):
    heap = []
    answer, time_elapsed, i = 0, 0, 0 #정답 / 지나간 시간 / 인덱스
    time_start = -1 # 시작할 시간
    
    while i < len(jobs): #모든 작업만큼 (개수 만큼)
        for job in jobs: #매번 jobs에서 탐색할 건데, 그게 뭐냐면
            if time_start < job[0] <= time_elapsed: #시작할 수 있는 시간이 현재 시간보다 크고, 지나간 시간보다 작다면(시작할 수 있는 범위에 있다면)
                h.heappush(heap, [job[1], job[0]]) #최소 힙의 성질을 이용, 작업시간 : 시작시간 으로 힙에 넣는다.
        if len(heap) > 0: # 만약 실행해야 하는 작업이 힙에 있다면
            time_start = time_elapsed # 여태까지 지나온 시간이 이제 시작시간이 되는 것이고
            time_work, time_wait = h.heappop(heap) # 가장 적은 작업시간을 pop해서
            time_elapsed += time_work # 지나갈 시간에 더해주고
            answer += (time_elapsed - time_wait) # 시작할 수 있는 시간부터 작업이 완료되기까지의 시간을 정답에 더한다
            i += 1 #실행한 작업의 개수를 증가시킨다.
        else:
            time_elapsed += 1 #만약 현재 지나온 시간에서 실행할 수 있는 작업이 없다면 1초씩 경과시킨다.

    return answer // len(jobs)

문제에서 요구되는 로직은 찾았지만, 구현하는 데에 어려움을 겪다가 풀이 방법을 참고하고 다시 짜봤다.

 

이 문제에서 가장 포인트가 되는 부분은 for문과 if 문을 이용해서 jobs에서 현재 실행 가능한 작업들을 작업시간을 기준으로 힙에 넣는 것이다.

문제에서 요구되는 값을 가장 작게 만드려면, 매 과정에서 실행할 수 있는 시간 중 작업시간이 가장 작은 작업을 먼저 수행해야하기 때문이다.

그래서, 힙에 실행 가능한 작업들을 넣는 push하는 것 자체가 작업시간별로 정렬을 하는 것이고, if 분기를 통해서 힙에 실행 가능한 작업이 있다면 그것을 pop해서 시간을 재는 것이다(작업시간이 최소인 것이 보장되어 있으므로)

그렇게 한 가지씩 매 상황에서 최적의 작업을 실행하는 것이 문제의 포인트였다.

---

<이중우선순위큐>

문제의 조건은 다음과 같다.

 

힙에 명령이 주어지는데, I 인 경우 그 값을 input / D 1 인경우 최대값을 delete / D -1인 경우 최소값을 delete 해야 한다.

원소가 없다면 [0, 0]을 반환하고, 그렇지 않다면 [최대값, 최소값]을 반환한다.

import heapq as h

def solution(operations):
    heap = []

    for op in operations: # 각 연산을 체크한다
        if op[0] == 'I': #만약 인풋이라면
            h.heappush(heap, int(op[2:])) #'I '다음의 값을 정수형으로 변환, 힙에 넣는다
        elif op[0] == 'D' and op[2] == '1': # 최대값을 제거해야하는 것이라면
            if len(heap) > 0: #힙에 원소가 있다면
                heap.pop() #가장 마지막 인덱스에 있는 값을 pop한다 - 최소 힙의 성질로 인해 최대값 보장
        else:
            if len(heap) > 0: # 최소값을 제거하는 것이라면
                h.heappop(heap) # 최소 힙의 성질을 이용, heappop한다.
    
    if len(heap) == 0: # 명령을 모두 수행하고, 원소가 없다면
        return [0, 0]
    else: # 그게 아니라면
        return [max(heap), min(heap)]

맞긴 했는데 다른 사람들의 풀이를 보니까 뭔가 느낌이 다르다.

야매로 운 좋게 통과한 것인가..? 싶어서 찾아보니, 최소 힙 / 최대 힙으로 구분해서 제거할 값을 정해놓은 글을 보았다.

이대로 푼 것이 정확한 풀이라면, 내가 생각했던 최소 힙의 마지막 원소가 최대값임이 보장된다는 정보가 틀린 것 인가? 하는 의문이 들었다.

 

위 그림에서, 마지막의 8과 9의 위치가 바뀌어도 각자의 부모 노드보다는 자신이 크기 때문에, 최소 힙의 성질이 유지된다.

이 말인 즉슨, 마지막 인덱스가 항상 최대값을 보장하지는 못 한다는 것이고, 따라서 명확하게 맞게 풀려면 위의 글에서 한 것 처럼 최대 힙을 따로 정해서, '-'를 이용해서 최대 값을 추적하는 것이 맞다.

== 나는 운 좋게 푼 것

---

디스크 컨트롤러 문제가 가장 어려웠다.

'어? 왜 벌써 풀리지'를 항상 경계하자.