1. 디스크 컨트롤러
- 난이도
- Level 3
- 출처
A. 📜 문제
위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.
B. 💡 내 답안
a. 😅 1차 시도 (실패)
import heapq
def solution(jobs):
jobs.sort(key=lambda x: [-x[0], -x[1]])
wait_queue = [jobs.pop()[::-1]]
acc = 0
work_count = 0
answer = 0
while wait_queue:
time = heapq.heappop(wait_queue)
acc += time[0]
work_count += 1
answer += (acc - time[1])
while jobs:
if jobs[-1][0] <= acc:
heapq.heappush(wait_queue, jobs.pop()[::-1])
else:
if len(wait_queue) == 0:
temp = jobs.pop(0)[::-1]
heapq.heappush(wait_queue, jobs.pop()[::-1])
acc = temp[1]
break
return answer // work_count
## 틀린 테스트 케이스
print(solution([[1, 10], [3, 3], [10, 3]])) # 9
print(solution([[24, 10], [18, 39], [34, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]])) # 74
b. 😅 2차 시도 (실패)
import heapq
def solution(jobs):
jobs.sort(key=lambda x: [x[0]])
work_count = len(jobs)
temp = jobs.pop(0)[::-1]
wait_queue = [temp]
acc = temp[1]
answer = 0
while wait_queue:
time = heapq.heappop(wait_queue)
acc += time[0]
answer += (acc - time[1])
while jobs:
if jobs[0][0] <= acc:
heapq.heappush(wait_queue, jobs.pop(0)[::-1])
else:
if len(wait_queue) == 0:
temp = jobs.pop(0)[::-1]
heapq.heappush(wait_queue, temp)
acc = temp[1]
break
return answer // work_count
## 틀린 테스트 케이스
print(solution([[24, 10], [18, 39], [34, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]])) # 74
b. 😅 3차 시도 (성공)
import heapq
def solution(jobs):
jobs.sort()
work_count = len(jobs)
temp = jobs.pop(0)[::-1]
wait_queue = [temp]
acc = temp[1]
answer = 0
while wait_queue:
time = heapq.heappop(wait_queue)
acc += time[0]
answer += (acc - time[1])
while jobs:
if jobs[0][0] <= acc:
heapq.heappush(wait_queue, jobs.pop(0)[::-1])
else:
if len(wait_queue) == 0:
temp = jobs.pop(0)[::-1]
heapq.heappush(wait_queue, temp)
acc = temp[1]
break
return answer // work_count
b. 😅 4차 시도 (성공 - 비효율성 제거)
import heapq
def solution(jobs):
jobs.sort(key=lambda x:[-x[0], -x[1]])
work_count = len(jobs)
temp = jobs.pop()[::-1]
wait_queue = [temp]
acc = temp[1]
answer = 0
while wait_queue:
time = heapq.heappop(wait_queue)
acc += time[0]
answer += (acc - time[1])
while jobs:
if jobs[-1][0] <= acc:
heapq.heappush(wait_queue, jobs.pop()[::-1])
else:
if len(wait_queue) == 0:
temp = jobs.pop()[::-1]
heapq.heappush(wait_queue, temp)
acc = temp[1]
break
return answer // work_count
a. 🙄 회고
내 풀이
- 풀이가 맞다고 생각했다.
- 풀이는 맞았다. 다만 디테일한 부분들이 틀렸다.
- acc의 초기값이라던지, jobs의 정렬 방식이라던지..
반성
- 문제를 더 잘 이해해야겠다. 그것밖에 없다.
C. 🧐 문제 해설
이해한 내용을 바탕으로 작성했습니다.
이 문제는 SJF 스케줄링 문제이다.
job 하나가 끝나면 그 중 가장 적게 걸리는 job을 실행하는 방식이다.
고려할 부분은 다음과 같다.
- 처음 시작할 job
- job A와 job B가 연결되는 경우
- job A가 실행되는 중에 job B가 들어오는 경우
- job A와 job B가 연결되지 않는 경우
- job A가 끝난 이후에 job B가 들어오는 경우
나는 고려할 부분 2번은 if jobs[-1][0] <= acc로 처리하였고, 3번은 if len(wait_queue) == 0으로 처리했다. 그리고 acc를 새로 뽑은 job의 시작 시간으로 갱신하였다.
코드를 작성할 때, 주의할 점은 acc의 초기값이다. 문제의 테스트 케이스에서는 job이 0초부터 시작하기 때문에 아주 쉽게 '모든 job은 0부터 시작할 것이다.'라는 편견을 갖기 쉽다. 하지만, job이 10초부터 시작한다면, 어떻게 할 것인가? 이 물음에 답할 수 있다면, 이 문제는 쉽게 해결할 수 있다.
더 많은 테스트 케이스는 아래 참고문헌을 통해 확인할 수 있다 !.
참고문헌
[1] Heap. 코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 (programmers.co.kr). Programmers. (accessed Jan 21, 2022)
[2] Seoyoung Lee, [python] 디스크 컨트롤러 (Programmers) - LunaLunaఇ (seoyoung2.github.io). Github.io. (accessed Jan 21, 2022)
Ghost