[파이썬] 코딩테스트 문제 풀이 - 힙 문제 (프로그래머스)

Writer : Harim Kang

힙 문제 - 프로그래머스

• 우선순위 큐를 위해서 만들어진 자료구조로, 완전 이진 트리의 일종입니다.

• 여러 값들 중에서, 최댓값 또는 최솟값을 빠르게 찾도록 O(logn) 만들어진 자료구조입니다.

• 파이썬에서는 heapq 내장 라이브러리를 통해서 최소 힙을 제공합니다.

    import heapq

  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 의미합니다.

    

  • heapq.heappush(a, b) : a 배열을 힙으로 하여 b원소를 넣습니다.

  • heapq.heappop(a) : a 배열의 최솟값을 꺼냅니다.

해당 포스팅에서 푸는 문제는 아래의 4문제입니다.

1. 더 맵게
2. 라면공장
3. 디스크 컨트롤러
4. 이중우선순위큐

해당 문제들은 프로그래머스의 코딩테스트 연습 > 코딩테스트 고득점 kit > 힙에 모여있는 4문에 입니다.

https://programmers.co.kr/learn/courses/30/parts/12117

프로그래머스

1. 더 맵게 (Level 2)

문제

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

문제 요약

• 스코빌 지수 : 매운 정도
• 스코빌 지수를 K이상으로 만드는 것이 목적입니다.
• 지수가 낮은 두개의 음식을 아래의 방법으로 섞어서 새로운 음식을 만듭니다.
  • 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
• 모든 음식의 스코빌 지수가 K이상이 될 때까지 반복하여 섞습니다.
• scoville : 스코빌 지수를 담은 배열
• K : 원하는 목표 스코빌 지수
• 섞어야하는 횟수를 return값으로 찾는 문제입니다.

제한 사항

• 불가능한 경우에는 -1을 return합니다.

테스트 케이스

해결

• 스코빌 지수를 모두 힙에 삽입합니다.

• 반복문을 돌면서 가장 작은 지수를 하나 꺼냅니다.

• 이때, 꺼냈더니 힙이 비어있고(마지막 수라는 뜻) 해당 값이 기준인 k보다 작은 경우는 문제를 해결할 수 없는 경우이기 때문에 -1을 리턴합니다.

    if len(heap) < 1 and current < K:
          answer = -1
          break

• 위의 예외사항이 아닌 경우(계산이 가능한 경우)에는 현재의 스코빌 지수가 기준 이상인지를 판단합니다. 기준 이상인 경우에는 가장 작은 값이 기준 보다 큰 경우 이므로 나머지도 기준 이상이기때문에 해결이 완료된 것입니다.

• 현재 값이 기준 미만이면, 다음으로 작은 값을 힙에서 꺼내서 계산하여 다시 넣습니다.

코드

import heapq


def solution(scoville, K):
    answer = 0
    heap = []
    for h in scoville:
        heapq.heappush(heap, h)
    while True:
        current = heapq.heappop(heap)
        if len(heap) < 1 and current < K:
            answer = -1
            break
        if current >= K:
            break
        else:
            answer += 1
            next_node = heapq.heappop(heap)
            heapq.heappush(heap, current + next_node*2)

    return answer


sc = [1, 2, 3, 9, 10, 12]
k = 7
print(solution(sc, k))

2. 라면공장 (Level 2)

문제

https://programmers.co.kr/learn/courses/30/lessons/42629

문제 요약

• 공장은 하루에 밀가루 1톤이 필요합니다.
• 기존 공급 공장의 문제로 k일동안 해외에서 수입해야합니다.
• 해외 공장에서 공급 날짜와 수량을 알려주고, 최소한의 횟수로 밀가루를 공급받고자 합니다.
• stock : 현재 남은 밀가루
• dates : 밀가루 공급 일정
• supplies : 일정당 공급 가능 수량
• k : 기존 공급 공장이 공급 가능해지는 시점
• 최소 몇 번 해외로부터 수입해야하는지를 return하는 문제입니다.

제한 사항

• stock의 밀가루는 0일 이후부터 사용합니다.
• k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
• dates는 오름차순 정렬되어 있습니다. 작업 시작 전에 공급을 기준으로 합니다.
• 바닥나는 경우는 없습니다.

테스트 케이스

해결

• 현재 재고인 stock에 공급때마다 공급량을 추가해줍니다.
• stock이 k이상이 되는 경우에, 밀가루가 충분하다고 판단합니다.
• dates 배열을 돌면서 stock보다 낮은 공급일을 기준으로 pq라는 힙에 넣습니다. 이때, -(공급량)을 넣어서 절대값기준 내림차순이 되도록합니다.
• 현재 재고보다 적은 공급일의 공급량을 모두 힙에 넣습니다.
• pq에 넣은 값들중 가장 큰 수를 현재 재고에 추가하고, 공급횟수를 1 추가합니다.
• 재고가 충분해질때까지 위의 행동을 반복합니다.

코드

import heapq


def solution(stock, dates, supplies, k):
    answer = 0

    pq = []
    i = 0
    while stock < k:
        # 목표 : 재고가 k 이상이면 밀가루가 충분
        # 현재 재고가 k보다 작을 때
        while i < len(dates) and dates[i] <= stock:
            # 해당 반복문에는 반드시 1번은 들어온다. (제한 조건에 의해)
            # 날짜를 증가 시키면서 공급일보다 stock 이 커질 때
            # 즉, 공급일에 도달하면 해당 공급량을 heap 에 push 한다.
            heapq.heappush(pq, -supplies[i])
            i += 1
        # 현재 공급일까지의 공급량 중 가장 큰 수를 추가
        # 해당 공급량이 부족하면 반복
        stock += -heapq.heappop(pq)
        answer += 1

    return answer

3. 디스크 컨트롤러 (Level 3)

문제

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

문제 요약

• 한 번에 하나의 작업만을 수행가능한 하드디스크의 디스크 컨트롤러를 구현합니다.

• 아래와 같이 작업 요청이 들어옵니다.

  

• 이때 각 작업의 요청부터 종료까지 걸린 시간의 평균 최솟값을 찾는 문제입니다.

• 위의 예제의 경우, 아래의 방법이 최솟값일 때의 순서입니다.

  

    - A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
    - C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
    - B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)
    - 평균 : (3+7+17)/3 = 9ms

고려 사항

• 고려할 예외 사항이 아주 많습니다.
• jobs는 순서대로 되어있지 않을 수 있습니다.
• 작업의 도착시간이 0으로 같은 경우가 있을 수 있습니다.
• 또한 작업이 끝났는데 대기중인 작업이 없이 쉬는 간격이 생길 수 있습니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
• jobs : 각 작업의 [작업 요청 시점, 작업 소요시간]을 담은 2차원 배열입니다.
• 작업 요청부터 종료까지 걸린 시간의 평균 최솟값을 return하는 문제입니다.

테스트 케이스

• 추가 케이스(예외사항 체크)
  1. jobs : [[0, 9], [0, 4], [0, 5], [0, 7], [0, 3]] , return : 13
  2. jobs : [[0, 3], [4, 4], [5, 3], [4, 1]] , return : 3

해결

• 우선, 작업들의 시작시간은 변하지 않습니다. 즉, 작업의 종료시간만을 고려하여 평균을 계산하면 됩니다.
• 작업의 종료시간은 현재 시간을 기준으로 남은 작업들 예측값을 구해서 힙에 넣어서 pop으로 꺼내면 가장 작은 기대값 작업을 꺼낼 수 있습니다.
• jobs 배열을 힙으로 변경하여서 시간 순서로 정렬합니다.
• pq : 현재 시간에서 소요 시간을 추가한 기대값을 기준으로 정렬하는 큐입니다.
• pq에서 꺼내면 해당 작업을 완료했다는 의미입니다.
• current : 꺼낸 작업이 끝난 시점입니다.
• 작업을 완료하였으므로, answer에 시작 시간을 빼고, 끝난 시점을 더해줍니다.
• 이제 새로운 작업을 찾기 위해 pq를 비우고, jobs에 남은 작업들을 넣습니다.
• jobs의 남은 작업들 중에, current 보다 작은 것들을 빼서 pq에 그 작업 이후 기대값을 계산하여 넣어줍니다.
• 기대값이 가장 낮은 작업이 반복문을 거치면서 하나씩 선정되어 나올 것 입니다.
• 만약 pq가 비었는데 jobs가 존재한다면, 도착한 작업이 없고 대기 작업이 존재하는 빈 공간이 생긴다는 의미이므로, 가장 도착 시간이 작은 작업을 pq로 옮겨줍니다.

코드

import heapq


def solution(jobs):
    n = len(jobs)
    # jobs 를 p_queue 로 변경 --> jobs 가 들어오는 순서대로 정렬된다.
    heapq.heapify(jobs)
    # 맨 처음꺼 꺼내보겠음 --> 젤 처음 시작하는게 나오겠지>?
    current, length = heapq.heappop(jobs)
    answer = 0
    pq = []
    # pq 라는 큐를 하나 더 사용해보겠음, 이건 현재 값에서 작업 길이를 추가한 걸로 정렬
    # 즉, 예측했을 때 결과 값을 오름차순
    # 맨처음 꺼를 pq에 넣어보겠음
    heapq.heappush(pq, (current + length, current, length))
    while pq:
        # pq에 있는 첫번째꺼(계산 값이 젤 작은 거)를 꺼냅니다.
        # current 는 선택한 작업이 끝난 시점
        current, start, length = heapq.heappop(pq)
        # answer 계산
        answer = answer - start + current
        while pq:
            # 여기 반복문은 pq를 비우고 jobs 에 채웁니다.
            _, c, d = heapq.heappop(pq)
            heapq.heappush(jobs, [c, d])
        while jobs:
            # jobs 에 남은 작업 중에 시작점이 current 보다
            # 작은 것들을 빼서 pq에 계산해서 넣어보겠슴
            if jobs[0][0] > current:
                # jobs 중 젤 작은게 current 보다 작아지면 반복문을 벗어나
                if not pq:
                    # 만약에 pq가 비었는데 jobs 는 존재할때,
                    # 즉, 도착한 작업이 없고 대기 작업은 존재할때
                    e, f = heapq.heappop(jobs)
                    heapq.heappush(pq, (e+f, e, f))
                break
            else:
                # current 보다 시작점이 작으면 가능한 경우이기 때문에 pq에 넣어봄
                a, b = heapq.heappop(jobs)
                heapq.heappush(pq, (current + b, a, b))

    answer /= n
    # 마무리

    return int(answer)

4. 이중우선순위큐 (Level 3)

문제

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

문제 요약

• 이중 우선순위 큐는 아래 연산만을 수행합니다.
  1. I 숫자 : 큐에 주어진 숫자를 삽입하는 명령어 입니다.
  2. D 1 : 큐에서 최댓값을 삭제하는 명령어 입니다.
  3. D -1 : 큐에서 최솟값을 삭제하는 명령어 입니다.
• operations : 연산들이 들어있는 배열입니다.
• operations의 순서대로 연산을 수행한 후, 큐가 비어있으면 [0, 0], 원소가 존재하면, [최댓값, 최솟값]을 return합니다.

제한 사항

• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

테스트 케이스

해결

• heapq는 최솟값부터 오름차순으로 정렬되는 자료구조입니다.
• pq : 오름차순 힙입니다.
• max_pq : pq와 다른점은 -값을 붙여서 -(최댓값)이 맨 앞에 오는 힙 구조입니다.
• insert(num) : num을 pq에 넣고, max_pq에는 -num으로 넣습니다.
• delete(a, b) : 매개변수는 모두 힙입니다. a가 max_pq이고, b가 pq이면 최댓값을 삭제하고, 반대의 경우에는 최솟값을 삭제합니다.
• pq에서 꺼낸 값은 최솟값이며, max_pq에서 꺼내서 -를 붙이면 최댓값입니다.

코드

import heapq


def solution(operations):

    pq = []
    max_pq = []

    def insert(num):
        heapq.heappush(pq, num)
        heapq.heappush(max_pq, -num)

    def delete(a, b):
        # a 가 max_pq 이고, b가 pq 이면 최댓값 삭제
        # 반대의 경우엔 최솟값 삭제
        if a and b:
            target = -heapq.heappop(a)
            temp = []
            while b:
                c = heapq.heappop(b)
                if target == c:
                    break
                else:
                    temp.append(c)
            if temp:
                for d in temp:
                    heapq.heappush(b, d)

    for op in operations:
        op = op.split()
        op[1] = int(op[1])
        if op[0] == 'D':
            if op[1] == 1:
                delete(max_pq, pq)
            elif op[1] == -1:
                delete(pq, max_pq)
        elif op[0] == 'I':
            insert(op[1])

    if pq:
        min_num = heapq.heappop(pq)
        max_num = -heapq.heappop(max_pq)
    else:
        min_num, max_num = 0, 0
    answer = [max_num, min_num]
    return answer