코딩 테스트/Level 3
디스크 컨트롤러
컴닥
2020. 9. 13. 15:09
반응형
디스크 컨트롤러
힙(Heap)
2346명 완료
https://programmers.co.kr/learn/courses/30/lessons/42627
코딩테스트 연습 - 디스크 컨트롤러
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를��
programmers.co.kr
힙은 쓰지도 않았는데... 왜 통과가...?
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 모듈
파이썬에서는 heapq라는 이진트리 모듈이 있습니다. ^^ https://docs.python.org/ko/3.7/library/heapq.html 먼저 heap이라는 자료구조를 알아야 하는데요. https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC..
comdoc.tistory.com
직관성을 위해 매시간 단위를 반복하여 시간의 흐름에 따라 시뮬레이션해 보았다.
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 이하로 줄어들었다.
(프로그래머스의 실행시간은 실행할 때 마다 조금씩 바뀐다. 참고만....)
반응형