[프로그래머스] 고득점 kit - 힙(Heap) (Python/파이썬)

<문제 링크>

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

프로그래머스

 

<풀이 전략>

1. 더 맵게: 범위가 2 ~ 1,000,000이므로 우선순위큐(파이썬의 경우 힙큐)를 적절히 이용해서 구현해주면 된다.

 

2. 디스크 컨트롤러: 그리디 + 우선순위 큐 문제. 요청시점 순으로 정렬하고 우선순위 큐를 이용해 다음 작업을 추출해서 현재 진행중인 작업 + 누적 시간을 계속 갱신해주면 된다. 소요 시간 순으로 추출하기 위해 힙에 넣을 때 순서를 뒤집어서 넣어줘야된다.

 

3. 이중우선순위큐: 최대힙만 잘 구현하면 어렵지 않다.

 

<정답 코드>

# 1. 더 맵게

import heapq

def solution(scoville, K):
    
    # 우선순위큐
    heapq.heapify(scoville)
    
    # 섞기
    def mix(scoville):    
        # 가장 덜 매운 2개 우선순위큐로 추출
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        
        # 섞기
        heapq.heappush(scoville, first + second * 2)
        
        return scoville

    answer = 0
    
    while True:

        # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우
        if len(scoville) == 1 and K > scoville[0]:
            answer = -1
            break
        
        # 모든 음식의 스코빌 지수가 K이상이 되었을 때
        if scoville[0] >= K:
            break
        
        # 섞기
        scoville = mix(scoville)
        
        answer += 1


    return answer

 

# 2. 디스크 컨트롤러

import heapq

def solution(jobs):
    answer = 0
    
    # idx: 작업 번호, time: 현재 진행중인 작업 마무리 시간
    idx = 0
    time = 0 
    
    # 처리한 작업 개수
    cnt = 0
    
    # 요청 시점 순으로 정렬
    jobs.sort()
    
    # 작업 대기 큐
    heap = []
    
    while len(jobs) > cnt:
        
        # 아직 큐에 올라가지 않는 작업이 있을 때
        if idx < len(jobs):
            for i in range(idx, len(jobs)):
                # 요청 시간이 현재 작업 마무리 시간 이전일 경우 (이어서 바로 할 수 있는 경우)
                if jobs[i][0] <= time:
                    # 소요시간, 요청시간 순으로 넣기
                    heapq.heappush(heap, jobs[i][::-1])
                    idx = i + 1
        
        # 큐에 작업이 있을 경우
        if heap:
            # current: 현재 진행할 작업 큐에서 빼기
            current = heapq.heappop(heap)
            
            # 마무리 시간 계산
            time += current[0]
            
            # 대기 시간 계산
            answer += time - current[1]
            
            cnt += 1
        
        # 큐에 작업이 없는 경우 바로 작업 등록하기
        elif idx < len(jobs):
            time  = jobs[idx][0]
    
    # 평균 계산
    answer //= len(jobs)

    return answer

 

# 3. 이중우선순위큐

import heapq


def solution(operations):
    answer = [0, 0]
    heap = []
    
    
    for operation in operations:
        
        # 삽입 연산자
        if operation[0] == 'I':
            heapq.heappush(heap, int(operation[2:]))
        
        # 삭제연산자
        else:
            if not heap:
                continue
            
            # 최솟값 삭제
            if operation[2] == '-':
                heapq.heappop(heap)
            # 최댓값 삭제
            else:
                heap.remove(max(heap))
    
    # 정답 반환
    if heap: 
        answer = [max(heap), min(heap)]

    return answer