디스크 컨트롤러

 

문제

---

문제가 조금 복잡해서 링크를 첨부하겠다.

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

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

 

풀이

---

전공자거나 운영체제의 스케쥴링 부분을 공부한 사람이라면 소요시간이 작은 작업을 우선적으로 처리하는 것이 최적의 경우라는 것을 알 것이다. 우선순위큐를 이용하면 되는데 약간은 복잡한 조건을 고려해주어야 한다. 그러나 단순히 소요시간 기준으로 정렬해 처리하면 다른 조건들을 고려하지 못한다. 생각의 순서는 다음과 같다.

1. 요청시점 순으로 오름차순 정렬 후 소요시간 순으로 오름차순 정렬을 해 첫 번째 원소를 첫 번째 작업으로 할당

2. 하나의 작업을 배정하는 매 순간 현재 시간을 계산해준다.(예컨대, 첫 번째 작업의 요청시간이 0, 소요시간이 3이라면 첫 번째 작업 배정 후 현재시간은 3이다.)

3. 반복문으로 탐색하며 '현재 시간에서 가능한 작업' 중 소요시간이 짧은 것을 우선적으로 배정한다.

4. 이 때, 주의할 점이 현재시간이 요청시간이 가장 빠른 작업의 요청시점보다 작은 경우는 현재시간을 해당 작업의 요청시점으로 갱신한다.(예컨대, 현재시간은 3인데 요청시간이 가장 빠른 작업의 요청시점이 5라면 시간이 더 지나야 작업을 할당할 수 있기 때문에)

def solution(jobs):
    answer = 0
    # 요청시점 순으로 오름차순 정렬 후 소요시간 순으로 오름차순 정렬
    s_jobs = sorted(jobs, key = lambda x : (x[0],x[1]))
    now_time = 0 # 현재 시간 기록
    first_job = s_jobs.pop(0)
    now_time = first_job[0]+first_job[1]
    answer += now_time - first_job[0]
    s_jobs = sorted(s_jobs, key = lambda x : x[1])
    while s_jobs:
        temp = sorted(s_jobs, key = lambda x : x[0])
        if now_time < temp[0][0]:
            # 요청시간이 가장 빠른 작업의 요청시간보다 현재 시간이 더 작은 경우
            now_time = temp[0][0]
        for job in s_jobs:
            if job[0] <= now_time:
                now_time += job[1]
                answer += now_time - job[0]
                s_jobs.remove(job)
                break
    return answer//len(jobs)