[프로그래머스] 디스크 컨트롤러

문제

출처

이해

입력

• jobs (작업 요청 배열)
  • 타입: 배열
  • 크기: [1, 500]
  • 원소 (작업 요청)
    • 타입: 배열
    • 형태: [int A, int B]
    • A 범위: [0, 1000]
    • B 범위: [1, 1000]
    • 의미: A시점에 B만큼의 시간이 소요되는 작업이 요청됨

출력

• 작업 요청부터 종료까지 걸린 시간의 평균을 최소화한 경우의 그 값 (소수점 이하 버림)

조건

1. 한 번에 하나의 작업만 수행 가능
2. 작업을 하지 않고 있다면 먼저 요청이 들어온 작업부터 처리함

예시

입력

[[0, 3], [1, 9], [2, 6]]

출력

9

접근

어떤 문제들은 문제에 대한 흥미를 높이기 위하여 추상적인 문제를 현실 세계의 대상에 빗대곤 한다. 많은 경우 이런 문제들은 A라는 이름을 B로 치환하는 것이 전부이다. 즉, 빗대어 표현한 대상에 대한 디테일이 떨어지는 경우가 많다는 것이다. 그래서 이런 문제를 많이 풀어본 사람들은 중요한 문장 몇 개만 보고 출제자가 어떤 알고리즘을 물어보는지를 알아내려는 경향이 있다. 그런데 이 문제는 문제를 훑어보는 사람들이 골탕먹기 딱 좋은 문제이다. 문제를 예시까지 아주 꼼꼼히 읽어야 풀 수 있기 때문이다.

우선 예시를 보면 모든 정보를 알 때 최적해를 구하는 문제인 것처럼 보인다. 하지만 사실 그렇지 않은데 조건 2에서 하드디스크는 현재까지 요청된 작업들에 대한 정보만 알고 있다는 것을 알 수 있다. 주어진 예시가 우연히 첫 번째로 요청된 작업이 끝나기 전에 모든 작업이 들어온 것 뿐이다. 즉, 이 문제는 시간에 대한 시뮬레이션으로 접근해야 한다.

문제에서 원하는대로 소요시간의 평균을 최소화하려면 현재 작업 목록에 있는 작업 중 소요시간이 가장 짧은 작업을 찾아야 한다. 작업 목록을 우선순위 큐로 하고 우선순위를 작업 소요시간으로 하면, 가장 짧은 작업을 log(n)에 찾을 수 있고, 입출력도 마찬가지로 log(n)에 가능하여 효율적이다.

현재 작업과, 요청된 작업 목록이 존재한다고 하자. 이제 다음과 같은 알고리즘을 생각해볼 수 있다.

1. 현재 작업이 끝나는 시점으로 이동한다.
2. 이동한 시점까지 요청된 모든 작업을 요청된 작업 목록에 추가한다.
   • 요청된 작업 목록이 비어있을 때 요청된 작업은 무조건 추가한다. (조건 2)
3. 요청된 작업 목록에서 가장 짧은 작업을 찾아서 현재 작업으로 한다.
4. 남아있는 작업이 없을 때까지 1~3을 반복한다.

실수하기 쉬운 부분은 작업을 하지 않고 있을 때 여러 개의 작업이 동시에 들어온다면 작업의 소요시간이 빠른 것을 먼저 처리해야 한다는 것이다. 이렇게 처리하면 조건 2에 위배된다고 생각하기 쉬운데, 잘 생각해보면 동시에 들어온 모든 요청들은 조건 2로 우선순위가 결정되지 않는다. 따라서 어떻게 처리하든 조건을 위배하지 않는다는 것을 알 수 있다.

구현

from queue import PriorityQueue

def solution(jobs):
    answer = 0

    # (작업 기간, 작업 요청 시간)을 받는 우선순위 큐
    q = PriorityQueue() 
    
    # 정렬 기준 1순위: 작업 요청 시점, 2순위: 작업 길이
    jobs.sort(key=lambda x : (x[0], x[1]))

    # 아직 처리 되지 않은 요청 중 가장 우선순위가 높은 요청의 인덱스
    job_idx = 1 

    # 현재 시간
    now_t = 0
    
    # 처음 작업을 큐에 추가함.
    q.put((jobs[0][1], jobs[0][0]))

    # 매 반복마다 1개의 작업을 마치고 새 작업을 받음.
    while True:
        # 작업 큐가 비면 종료한다.
        if q.empty():
            break
        
        # 다음 작업을 현재 작업으로 한다.
        nxt_dur, nxt_req = q.get()
        job_req, job_start, job_dur = nxt_req, max(nxt_req, now_t), nxt_dur
        now_t = job_start + job_dur
        answer += now_t - job_req
        
        # 다음 작업이 끝나는 시점까지 요청되는 모든 작업을 큐에 넣는다.
        cnt = 0
        for req, dur in jobs[job_idx:]:
            if req > now_t and not q.empty():
                break
            q.put((dur, req))
            cnt += 1
        job_idx += cnt
        
    return answer // len(jobs)