디스크 컨트롤러

디스크 컨트롤러
힙(Heap) 
2346명 완료

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

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

힙은 쓰지도 않았는데... 왜 통과가...? 

def solution(jobs):
    total_time = end = total_wait = 0
    length = len(jobs)
    for job in jobs:
        total_time += job[1]
    for now in range(total_time + 1):
        if now >= end and jobs:
            temp = [index for index, job in enumerate(jobs) if job[0] <= now]
            if temp:
                shortest = total_time
                shortest_index = 0
                for index in temp:
                    if shortest >= jobs[index][1]:
                        shortest = jobs[index][1]
                        shortest_index = index
                total_wait += now - jobs[shortest_index][0] + jobs[shortest_index][1]
                end = jobs[shortest_index][1] + now
                jobs.pop(shortest_index)
    return total_wait // length

테스트 1 〉	통과 (22.06ms, 9.57MB)
테스트 2 〉	통과 (17.98ms, 9.54MB)
테스트 3 〉	통과 (14.76ms, 9.52MB)
테스트 4 〉	통과 (14.36ms, 9.53MB)
테스트 5 〉	통과 (20.20ms, 9.53MB)
테스트 6 〉	통과 (0.68ms, 9.51MB)
테스트 7 〉	통과 (12.58ms, 9.64MB)
테스트 8 〉	통과 (9.67ms, 9.69MB)
테스트 9 〉	통과 (3.58ms, 9.43MB)
테스트 10 〉	통과 (23.98ms, 9.5MB)
테스트 11 〉	통과 (0.05ms, 9.55MB)
테스트 12 〉	통과 (0.07ms, 9.71MB)
테스트 13 〉	통과 (0.07ms, 9.48MB)
테스트 14 〉	통과 (0.04ms, 9.5MB)
테스트 15 〉	통과 (0.05ms, 9.55MB)
테스트 16 〉	통과 (0.02ms, 9.67MB)
테스트 17 〉	통과 (0.02ms, 9.55MB)
테스트 18 〉	통과 (0.02ms, 9.51MB)
테스트 19 〉	통과 (0.02ms, 9.61MB)
테스트 20 〉	통과 (0.01ms, 9.52MB)

정리를 해야겠다.. 

heapq를 사용... 

https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-heapq-%EB%AA%A8%EB%93%88

파이썬의 heapq 모듈

직관성을 위해 매시간 단위를 반복하여 시간의 흐름에 따라 시뮬레이션해 보았다. 

def solution(jobs):
    from heapq import heappush, heappop
    jobs.sort(reverse=True)
    total_time = end = total_wait_run = 0
    length = len(jobs)
    que = []
    for job in jobs:
        total_time += job[1]
    for now in range(total_time + 1):
        while jobs and jobs[-1][0] <= now:
            start, running = jobs.pop()
            heappush(que, (running, start))
        if now >= end:
            if que:
                running, start = heappop(que)
                total_wait_run += now - start + running
                end = now + running
    return total_wait_run // length

같은 시간을 기준으로 하였지만 total_time 변수를 쓰지 않고 코딩할 수 있다. 
매 시간을 반복하는 스타일로는 이 정도가 가장 깔끔한 것 같다. 

def solution(jobs):
    from heapq import heappush, heappop
    jobs.sort(reverse=True)
    now = end = total_wait_run = 0
    length = len(jobs)
    que = []
    while jobs or que:
        while jobs and jobs[-1][0] <= now:
            start, running = jobs.pop()
            heappush(que, (running, start))
        if now >= end:
            if que:
                running, start = heappop(que)
                total_wait_run += now - start + running
                end = now + running
        now += 1
    return total_wait_run // length

테스트 1 〉	통과 (12.82ms, 7.75MB)
테스트 2 〉	통과 (11.21ms, 7.78MB)
테스트 3 〉	통과 (10.10ms, 7.77MB)
테스트 4 〉	통과 (9.08ms, 7.76MB)
테스트 5 〉	통과 (11.03ms, 7.77MB)
테스트 6 〉	통과 (0.90ms, 7.75MB)
테스트 7 〉	통과 (8.81ms, 7.79MB)
테스트 8 〉	통과 (7.98ms, 7.84MB)
테스트 9 〉	통과 (2.56ms, 7.77MB)
테스트 10 〉	통과 (13.55ms, 7.79MB)
테스트 11 〉	통과 (0.06ms, 7.73MB)
테스트 12 〉	통과 (0.08ms, 7.75MB)
테스트 13 〉	통과 (0.07ms, 7.75MB)
테스트 14 〉	통과 (0.04ms, 7.84MB)
테스트 15 〉	통과 (0.05ms, 7.72MB)
테스트 16 〉	통과 (0.02ms, 7.84MB)
테스트 17 〉	통과 (0.01ms, 7.76MB)
테스트 18 〉	통과 (0.02ms, 7.84MB)
테스트 19 〉	통과 (0.02ms, 7.79MB)
테스트 20 〉	통과 (0.01ms, 7.7MB)

이제 마지막 단계.. 매초 반복을 없애보자.
어차피 각 job의 끝(end)에 도달해야 새로운 일을 받을 수 있으니... 

이런 느낌으로 바꾸면 된다 마지막의 now = end로... 
물론 작동하지 않는다. 시간 초과.. 

# 작동 안 됨.

def solution(jobs):
    from heapq import heappush, heappop
    jobs.sort(reverse=True)
    now = end = total_wait_run = 0
    length = len(jobs)
    que = []
    while jobs or que:
        while jobs and jobs[-1][0] <= now:
            start, running = jobs.pop()
            heappush(que, (running, start))
        if now >= end:
            if que:
                running, start = heappop(que)
                total_wait_run += now - start + running
                end = now + running
        now = end
    return total_wait_run // length

생각해 보면 중간에 작업이 끊어진 (que는 비었는데 jobs는 남은) 경우 무한 루프로 빠지는 것을 알 수 있다. 

이 부분만 else를 이용해 고쳐주고 변수명들을 정리해주자. 

def solution(jobs):
    from heapq import heappush, heappop
    jobs.sort(reverse=True)
    que = []
    now, total_wait_run, length = 0, 0, len(jobs)
    while jobs or que:
        while jobs and jobs[-1][0] <= now:
            start, running = jobs.pop()
            heappush(que, (running, start))
        if que:
            running, start = heappop(que)
            total_wait_run += now - start + running
            now = now + running
        else:
            now = jobs[-1][0]
    return total_wait_run // length

테스트 1 〉	통과 (0.77ms, 9.41MB)
테스트 2 〉	통과 (0.69ms, 9.46MB)
테스트 3 〉	통과 (0.57ms, 9.49MB)
테스트 4 〉	통과 (0.59ms, 9.4MB)
테스트 5 〉	통과 (0.77ms, 9.48MB)
테스트 6 〉	통과 (0.04ms, 9.51MB)
테스트 7 〉	통과 (0.53ms, 9.5MB)
테스트 8 〉	통과 (0.39ms, 9.52MB)
테스트 9 〉	통과 (0.15ms, 9.53MB)
테스트 10 〉	통과 (0.94ms, 9.57MB)
테스트 11 〉	통과 (0.02ms, 9.52MB)
테스트 12 〉	통과 (0.02ms, 9.54MB)
테스트 13 〉	통과 (0.02ms, 9.59MB)
테스트 14 〉	통과 (0.02ms, 9.42MB)
테스트 15 〉	통과 (0.02ms, 9.55MB)
테스트 16 〉	통과 (0.02ms, 9.55MB)
테스트 17 〉	통과 (0.02ms, 9.5MB)
테스트 18 〉	통과 (0.02ms, 9.55MB)
테스트 19 〉	통과 (0.02ms, 9.54MB)
테스트 20 〉	통과 (0.01ms, 9.6MB)

실행시간이 1ms 이하로 줄어들었다. 
(프로그래머스의 실행시간은 실행할 때 마다 조금씩 바뀐다. 참고만....)