[programmer-python] 힙

더 맵게

Try

테스트 케이스 몇 가지에서 에러도 나고, 효율성도 떨어진다고 나온다.

import heapq

def solution(scoville, K):
    if scoville[0] >= K:
        return 0

    mixCount = 0
    maxCount = len(scoville) - 1
    for _ in range(maxCount):
        if scoville[0] >= K:
            break
        mixCount += 1
        mix = heapq.heappop(scoville)*2 + heapq.heappop(scoville)
        heapq.heappush(scoville, mix)
        print(scoville)
        
    if mixCount == maxCount and scoville[0] < K:
        return -1

    return mixCount

srcList = [1, 2, 3, 9, 10, 12]
K = 7
heapq.heapify(srcList)
print(solution(srcList,K))

Answer

위에서 내가 틀린 이유는... 그냥 수식을 잘못썼다.
heap에서 2번째 pop할 때 2를 곱했어야 했는데 처음에 곱해서 틀렸다. 문제를 꼼꼼히 읽자

import heapq

def solution(scoville, k):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)
    mix_cnt = 0
    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        mix_cnt += 1
    return mix_cnt

srcList = [1, 2, 3, 9, 10, 12]
K = 7
print(solution(srcList,K))

디스크 컨트롤러

Try

2번째 인덱스를 기준으로 오름차순 정렬한 것을 정답이라 가성하고 푼 코드다.
정확도 100점 만점에 5점 나왔다! 하하

def solution(jobs):
    jobs = sorted(jobs, key=lambda x:x[1])
    length = len(jobs)
    sum = 0
    for index, job in enumerate(jobs):
        dur = 0
        for i in range(index+1):
            dur += jobs[i][1]
        dur -= job[0]
        sum += dur
    
    return sum // length

print(solution([[0, 3], [2, 6], [1, 9]]))

Answer

#coding:utf8

import heapq

def solution(jobs):
    count, last, answer = 0, -1, 0 # 처리 작업 수, 최근 작업 끝난 시간, 최소 평균
    heap = []
    jobs.sort()
    time = jobs[0][0] 
    while count < len(jobs): 
        for s, t in jobs: # 시작 시간, 소요 시간
            if last < s <= time:
                heapq.heappush(heap,(t,s))
        if len(heap) > 0:
            count += 1
            last = time
            term, start = heapq.heappop(heap)
            time += term
            answer += (time - start)
        else:
            time += 1

    return answer // len(jobs)

• 참조 : https://seoyoung2.github.io/algorithm/2020/06/04/Programmers-diskcontroller.html

이중우선순위큐

Try

정답이라고 나오긴 했는데 실행버튼 눌렀을 때 Test2에서 실패했었다.

#coding:utf8
import heapq

def solution(operations):
    heap = list()
    minBool = True
    for oper in operations:
        cmd, num = oper.split()
        if cmd == "I":
            if minBool == True:
                heap.append(int(num))
            else:
                heap.append((-int(num),int(num)))
        elif cmd == "D":
            if not heap:
                continue
            # 최소값 삭제
            if num == "-1":
                if not minBool:
                    temp = [i[1] for i in heap]
                    heap = temp
                heapq.heapify(heap)
                heapq.heappop(heap)
                minBool = True
            # 최대값 삭제
            elif num == "1":
                if minBool:
                    temp = []
                    for h in heap:
                        heapq.heappush(temp, (-h,h))
                    heap = temp
                heapq.heappop(heap)
                minBool = False

    if heap:
        if minBool:
            heapq.heapify(heap)
            min = heap[0]
            temp = []
            for h in heap:
                heapq.heappush(temp, (-h,h))
            max = temp[0][1]
        else:
            max = heap[0][1]
            temp = [i[1] for i in heap]
            heapq.heapify(temp)
            min = temp[0]
        return [max, min]
    else:
        return [0,0]

Answer

난 한 번 operation 돌 때마다 heap을 다시 만드는 식이라서, I 명령어일 때 heappush가 아니라 append를 해줘도 괜찮다고 생각했는데 아니었다. 내가 밑에서 minBool이 True일 때는 그냥 min=heap[0]이라고 처리했기 때문. 만약에 삭제 명령이 없었다면 heap이 되지않음

def solution(operations):
    heap = list()
    minBool = True
    for oper in operations:
        cmd, num = oper.split()
        if cmd == "I":
            if minBool == True:
                heapq.heappush(heap, int(num))
            else:
                heapq.heappush(heap, (-int(num),int(num)))
        elif cmd == "D":
            if not heap:
                continue
            # 최소값 삭제
            if num == "-1":
                if not minBool:
                    temp = [i[1] for i in heap]
                    heap = temp
                heapq.heapify(heap)
                heapq.heappop(heap)
                minBool = True
            # 최대값 삭제
            elif num == "1":
                if minBool:
                    temp = []
                    for h in heap:
                        heapq.heappush(temp, (-h,h))
                    heap = temp
                heapq.heappop(heap)
                minBool = False

    if heap:
        if minBool:
            min = heap[0]
            temp = []
            for h in heap:
                heapq.heappush(temp, (-h,h))
            max = temp[0][1]
        else:
            max = heap[0][1]
            temp = [i[1] for i in heap]
            heapq.heapify(temp)
            min = temp[0]
        return [max, min]
    else:
        return [0,0]

Reference

• 힙 모듈 사용법: https://www.daleseo.com/python-heapq/