[Python] 프로그래머스 코딩테스트 고득점 Kit - 힙

출처: GeeksforGeeks

---

 

1. 더 맵게 (Lv. 2)

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

# 이해
# 최소 힙
# 값이 작은 2개를 pop()해서, 특정 공식으로 계산된 결과를 push()
# 최소 값이 K를 넘을 때까지 반복

# 풀이
# scoville = heapq.heapify(scoville)
# cnt = 0
# while True:
    # scoville을 정렬하여, [0]번째 원소가 K보다 작으면 (heap은 subscription이 가능한가?)
        # first = heapq.heappop(scoville)
        # second = heapq.heappop(scoville)
        # new = first + (second * 2)
        # heapq.heappush(scoville, new)
        # cnt += 1
    # 작지 않으면 return cnt
    

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) >= 2:
        if scoville[0] < K:
            first = heapq.heappop(scoville)
            second = heapq.heappop(scoville)
            new = first + (second * 2)
            heapq.heappush(scoville, new)
            answer += 1
        else:
            return answer
    
    return answer if scoville[0] >= K else -1

 

힙의 크기가 1 이하가 되면, 더 이상 계산을 진행할 수 없으므로 while의 범위를 설정한다.

while을 벗어난 뒤에도 마지막으로 조건을 만족하는지 확인한 뒤에 결과를 return한다.

 

 

2. 디스크 컨트롤러 (Lv. 3)

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

# 이해 1
# 전체 작업 소요 시간의 평균이 최소가 되도록
# 매번 가능한 작업 중 소요 시간이 작은 것을 먼저 수행한다.
    # 반례가 있다.
    # [[0, 3], [4, 10], [5, 1], [6, 1]]
    # 3, 14, 15, 16 == 11.25
        # 3 + 10 + 10 + 10
    # 3, 6, 7, 17 == 8.25
        # 3, 1, 1, 10
# 끝나는 시간을 기준으로 해야 할 듯하다.
# 배열을 탐색하여, 원소 별로 끝나는 시간(시작 시간 + 소요 시간)을 구한다.
# 끝나는 시간이 빠른 것 순서대로 처리한다.

# 이해2
# 이해 1은 틀렸다 !! 정확히는 문제의 조건에 부합하지 않는다.
# <제한사항>의 마지막 항목: "하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다."
# 따라서 수행 가능한 작업이 있다면 즉시 실행한다.
# 수행 가능한 작업이 여러 개가 있다면 소요 시간이 짧은 것을 실행한다.

# 풀이
# 현재 시간을 표시할 변수 now = 0
# 총 대기 시간 변수 total_waiting_time = 0
# 현재 가능한 작업 큐 ready_queue = []
# 현재 index = 0

import heapq

def solution(jobs):
    jobs.sort()
    now = 0
    total_waiting_time = 0
    index = 0
    ready_queue = []

    while index < len(jobs) or ready_queue:
        while index < len(jobs) and jobs[index][0] <= now: # 현재 시간 now보다 작은(실행 가능한) 작업 모두 추가
            heapq.heappush(ready_queue, (jobs[index][1], jobs[index][0]))
            index += 1

        if ready_queue:
            duration, start = heapq.heappop(ready_queue)
            now += duration
            total_waiting_time += now - start
        else:
            now = jobs[index][0]

    return total_waiting_time // len(jobs)

 

3시간 이상 풀이한 듯하다 ..

적어도 1시간은 문제의 조건을 놓쳐서 헤맸다.

 

각 작업의 요청부터 종료 시간의 평균을 최소로 하려면, 작업이 종료되는 시간을 기준을 해야 한다고 판단했다.

가령 다음과 같은 테스트 케이스가 있다고 가정하자. `[[0, 3], [4, 10], [5, 1], [6, 1]]`

 

매 순간 가능한 작업 중 소요 시간이 가장 짧은 것을 선택하면 다음과 같다. `[0, 3] -> [4, 10] -> [5, 1] -> [6, 1]`

이 경우 요청부터 종료까지 3 + 10 + 10 + 10 -> 평균 8.25초가 소요된다.

 

끝나는 시간을 기준으로 가장 먼저 끝나는 작업을 선택하면 다음과 같다. `[0, 3] -> [5, 1] -> [6, 1] -> [4, 10]`

이 경우는 3 + 1 + 1 + 13 -> 평균 4.5초가 소요된다.

 

그러나 문제의 조건 중 다음을 놓쳤다. `하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.`

조건을 만족하려면, 반드시 `현재 가능한 작업 중 소요 시간이 가장 짧은 것을 선택`해서 수행하면 된다.

 

현재 작업의 시작 시간이 now 보다 작다면 ready_queue에 추가한다. `while index < len(jobs) and jobs[index][0] <= now:`

현재 작업의 시작 시간이 now 보다 크다면  now를 현재 작업의 시작 시간에 맞춘다. `else:`

 

 

3. 이중우선순위큐 (Lv. 3)

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

# 이해
# 명령어를 받아서 힙을 구성
# 명령어에 따라 최솟값 혹은 최댓값을 pop()
# 모든 명령어를 수행하고 남은 힙의 최솟값과 최댓값을 return

# 풀이
# 명령어의 순서를 미리 기록한다.
# 가령 최솟값 삭제면 False, 최댓값 삭제면 True
# 힙에 추가하는 명령어를 실행할 때마다, 순서 배열을 보면서 최댓값 삭제(True)인 경우 -값을 추가한다.
# 모든 명령어는 최솟값 삭제로 실행한다.

import heapq

def solution(operations):
    answer = []
    heap = []
    
    for operation in operations:
        op, num = operation.split()
        
        if op == "I":
            heapq.heappush(heap, int(num))
        elif heap:
            if num == "-1":
                heapq.heappop(heap)
            else: # num == "1"
                heap.remove(max(heap))
    
    return [0, 0] if len(heap) == 0 else [max(heap), min(heap)]

 

O(NlogN) 풀이가 떠오르지 않아서 구글링을 했다.
다들 그냥 remove 함수를 사용한다.

 

O(N^2) 아닌가...? N == 10 ** 6이니까 10 ** 12로, 시간 초과 기준(10 ** 9)을 아득히 넘는다.
완성된 힙을 탐색하는 것이 아니라, 완성해가면서 탐색하는 것이기 때문에 가능한가보다.

 

다시 한번 느꼈다. 프로그래머스에서 문제 풀 때는 시간 복잡도는 신경 쓰는 것이 아니다.
N이 1억이나 10억이면 이분 탐색 문제이고, 아니라면 일단 O(N ** 2)으로 풀이하자.