프로그래머스 레벨 3 디스크 컨트롤러

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42627#

접근 1)

현재 시간을 기준으로 요청 받은 시간에서 실행 종료 시간 까지을 기준으로 정렬한 후 첫번째 인덱스부터 꺼내서 처리하였다.-> 마지막 테케 뺴고 다 실패..
그 이유는 다음 문장에서 찾을 수 있음

• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

위 방식처럼 정렬했을때, 아직 요청시간에 도달하지 않은 작업들이 요청시간에 도달한 작업보다 먼저 시작할 수 도 있음. 다른 방법 ㄱ

접근 2)

정렬기준은 똑같으나, 요청 시간에 도달한 작업들 중에서만 실행되도록 로직을 바꾸엇음. 그러나 절반 실패.

접근 3)

그러다 문듣 다음과 같은 생각을 떠올리게됨.
모든 작업은 무조건 각자의 실행시간 만큼은 실행되어야함. 각각의 작업의 즉 현재 시간과 요청시간과의 차이값을 최대한으로 줄이는 것이 비로소 작업시간들의 최솟값임.

• 즉, 이미 요청시간에 도달한 작업들 중 가장 작업시간이 짧은것을 먼저 실행시켜야함 (그래야 나머지 작업시간들의 대기시간이 최소한으로 증가하니까)
• 부연설명 - 현재 시간이 n이라 하였을떄, n+a(작업이 끝난시간)이 최솟값이 되어야, 나머지 작업들의 총 대기시간이 최솟값이다.

코드

def solution(jobs):
    # 실행시간은 curtime-요청된 time + 실행시간 
    curtime=0
    total=0
    jobslen=len(jobs)
    while jobs:
        jobs.sort(key=lambda x:(x[1]))
        check=True
        for i in range(len(jobs)):
            if jobs[i][0]<=curtime:
                curjob=jobs[i]
                jobs.pop(i)
                total+=curtime-curjob[0]+curjob[1]
                curtime+=curjob[1]
                check=False
                break
        if check:
            curtime=100000
            for i in range(len(jobs)):
                curtime=min(curtime,jobs[i][0])
    return total//jobslen

복잡하게 생각하면 더 복잡한 문제였네요