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

[문제 링크]

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

[입출력 예]

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

[소스코드]

from collections import deque
def solution(jobs):
    import heapq
    # while 문 두 번 사용
    # 우선 요청 순서대로 정렬하고,
    # 하나 처리 후 현재까지 온 요청들을
    # 빨리 끝낼 수 있는 것부터 처리

    # 1. jobs 정렬
    # deque은 sort, sorted와 안맞는다.
    jobs=deque(sorted(jobs))
    # n은 처리한 요청 수
    answer = 0
    n = 0
    # 2. 최초 시간 설정
    # 시간을 따라가면서 작업을 진행한다.
    # 처리 시간은 현재시간-요청시간이다.
    # 처리시간의 합을 answer에 담는다.
    time = jobs[0][0]

    # 3. 우선순위 큐 생성
    pq = []

    # 4. job이 빌 떄까지 다음을 반복합니다.
    while jobs:
        # 1. jobs의 첫 원소를 꺼내옵니다.
        (request, expend) = jobs.popleft()
        # 2. n에 1을 더해줍니다.
        n += 1
        # 3. time에 소요 시간 expend를 더해줍니다.
        time += expend
        # 4. answer에 현재 시간 time에서 요청 시간 request를 뺸 값을 더해줍니다.
        answer += (time - request)

        # 5. jobs가 비지 않고, 이미 요청되어있는 작업들을 heapq에 푸쉬.
        while jobs and jobs[0][0] < time:

            # 1. jobs의 첫 원소를 꺼내옵니다.
            (request, expend) = jobs.popleft()

            # 2. 해당 원소를 expend 기준으로 pq에다 저장합니다.
            # expend 내림차순으로 저장.
            heapq.heappush(pq, (-expend, request))

        # 6. pq가 빌 떄까지 다음을 반복합니다.
        while pq:
            # 1. pq에서 원소를 꺼냅니다.
            (expend, request) = heapq.heappop(pq)
            # 2. jobs에 첫 원소로 저장합니다.
            # - 처리 되었기 때문에 한번 더 -해서 제대로.
            # appendleft를 하면 결국 처리시간이 큰것부터 들어가기때문에
            # 처리시간이 가장 작은 것이 가장 앞에 오게 된다.
            jobs.appendleft([request, -expend])

    # 5. answer에 n을 나눠준 몫을 저장하고 반환합니다.
    answer //= n
    return answer

다른 풀이

from collections import deque
def solution(jobs):
    import heapq
    # while 문 두 번 사용
    # 우선 요청 순서대로 정렬하고,
    # 하나 처리 후 현재까지 온 요청들을
    # 빨리 끝낼 수 있는 것부터 처리

    # 1. jobs 정렬
    # deque은 sort, sorted와 안맞는다.
    jobs=deque(sorted(jobs))
    # n은 처리한 요청 수
    answer = 0
    n = 0
    # 2. 최초 시간 설정
    # 시간을 따라가면서 작업을 진행한다.
    # 처리 시간은 현재시간-요청시간이다.
    # 처리시간의 합을 answer에 담는다.
    time = jobs[0][0]

    # 3. 우선순위 큐 생성
    pq = []

    # 4. job이 빌 떄까지 다음을 반복합니다.
    while jobs:
        # 1. jobs의 첫 원소를 꺼내옵니다.
        (request, expend) = jobs.popleft()
        # 2. n에 1을 더해줍니다.
        n += 1
        # 3. time에 소요 시간 expend를 더해줍니다.
        time += expend
        # 4. answer에 현재 시간 time에서 요청 시간 request를 뺸 값을 더해줍니다.
        answer += (time - request)

        # 5. jobs가 비지 않고, 이미 요청되어있는 작업들을 heapq에 푸쉬.
        temp=[]
        while jobs and jobs[0][0] < time:
            temp.append(jobs.popleft())
            temp.sort(key=lambda x:x[1])
        jobs=deque(temp)+jobs
        # deque을 계속 생성하는 건 좋지 않은 풀이 같다.

    # 5. answer에 n을 나눠준 몫을 저장하고 반환합니다.
    answer //= n
    return answer