[프로그래머스] 해시 2. 디스크 컨트롤러

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

코딩테스트 연습 - 디스크 컨트롤러

---

풀이

힙이 뭔지 그새 또 까먹어서 지난번 힙 문제를 보고왔다.

힙은 완전이진트리의 일종으로 최댓값, 최솟값을 추출하기 쉬운 자료구조였다.

 

포기한 방법들..

• max(0, 요청 시간 - 현재 시간 curTime) + 소요 시간 을 key로 갖는 최소 heap을 만든다 -> 현재 시간이 계속 바뀌니 문제가 될 것 같아서 포기
• 힙을 만드는 대신 min으로 위의 과정을 매번 계산한다. -> 로직에 문제가 있는 것 같아 포기

 

1. 현재 시간까지 들어온 작업 요청의 소요시간으로 힙을 만든다

2. 가장 작은 값을 빼내고 curTime 에 그 작업시간의 소요시간을 더한다.

3. 위 작업을 반복하다 모든 요청이 끝나면 종료한다.

import heapq

def solution(jobs):
    jobLen = len(jobs)
    curTime = 0
    total = 0
    waitingJobs = []
    heapq.heapify(waitingJobs)
    
    while True:
        for job in jobs[:]:           
            if job[0] <= curTime:
                heapq.heappush(waitingJobs, job[1])
                total -= job[0]
                jobs.remove(job)
        
        if len(waitingJobs) <= 0:
            return total/jobLen
        
        curTime += heapq.heappop(waitingJobs)
        total += curTime
        
        

    return total / jobLen

처참... 뭘잘못했을까

 

import heapq

def solution(jobs):
    jobLen = len(jobs)
    curTime = 0
    total = 0
    waitingJobs = []
    heapq.heapify(waitingJobs)
    
    while True:
        for job in jobs[:]:           
            if job[0] <= curTime:
                heapq.heappush(waitingJobs, job[1])
                total -= job[0]
                jobs.remove(job)
        
        if len(waitingJobs) <= 0:
            if len(jobs) > 0:
                curTime += 1
                continue;
            else:
                return total/jobLen
        
        curTime += heapq.heappop(waitingJobs)
        total += curTime
        
    
    return total / jobLen

현재 시간에 요청된 작업이 없을 때를 처리했다.

처참,,,

어디를 틀렸는지 모르겠어서 다른 사람 코드를 봤다.

근데 나랑 로직이 비슷해 보여서 설마..? 하고 마지막에 total / len을 total//len으로 바꿨더니

통과,,, 허무,,

최종 코드

import heapq

def solution(jobs):
    jobLen = len(jobs)
    curTime = 0
    total = 0
    waitingJobs = []
    heapq.heapify(waitingJobs)
    
    while True:
        for job in jobs[:]:           
            if job[0] <= curTime:
                heapq.heappush(waitingJobs, job[1])
                total -= job[0]
                jobs.remove(job)
        
        if len(waitingJobs) <= 0:
            if len(jobs) > 0:
                curTime += 1
                continue;
            else:
                return total//jobLen
        
        curTime += heapq.heappop(waitingJobs)
        total += curTime

---

다른 분의 코드

def solution(jobs):
    answer = 0
    start = 0  # 현재까지 진행된 작업 시간
    length = len(jobs)

    jobs = sorted(jobs, key=lambda x: x[1])  # 소요시간 우선 정렬

    while len(jobs) != 0:
        for i in range(len(jobs)):
            if jobs[i][0] <= start:
                start += jobs[i][1]
                answer += start - jobs[i][0]
                jobs.pop(i)
                break
            # 해당시점에 아직 작업이 들어오지 않았으면 시간 ++
            if i == len(jobs) - 1:
                start += 1

    return answer // length

힙을 안쓰셨다... ;; ;;; 첨에 이렇게 할까 하다가 문제되겠지 싶어서 안했는데 초간단

(https://johnyejin.tistory.com/132)

 

---

문법

1. 배열 순회 중 원소 삭제
for i in jobs:
    jobs.remove(i)

순회중에 원소를 삭제하면 정상적으로 순회되지 않음

for i in jobs[:]:

    jobs.remove(i)

배열 복사해서 순회시켜줘야함!