99클럽 코테 스터디 2일차 TIL + 힙 - 디스크 컨트롤러

 

🔗 프로그래머스 - 디스크 컨트롤러

운영체제 수업때 했던 내용이었으나 또 삽질을 했다.

정리하자면,

1. 하드디스크가 놀고 있을 때에는 먼저 요청된 작업부터 진행한다. - jobs 를 sort 해야 한다는 뜻
2. 하드디스크가 작업중일 때 요청이 들어오는 경우 작업 시간이 짧은 작업 순서로 대기열에 들어간다. - heap을 이용해 우선순위 정렬

 

삽질 했던 부분은

1. 대기열에 삽입 할 때, 요청된 시간 보다 현재 시간이 클 때로 잘못 적어놔서 (요청 시간 > time) 계속 틀렸었다 ▶ 부등호 잘 보기
2. 작업 시간이 0일 때 처리를 해주지 않아 틀렸었다. 
3. 처음 jobs를 sort 하지 않아 틀렸었다. 

 

+ 다른 분이 푸신 방법 중에 데크를 사용한 방법이 있었다. 실행속도가 굉장히 빨랐다. 데크는 처음 들어봐서 정리해 봤다.

deque: 양쪽 끝에서 빠르게 추가와 삭제를 할 수 있는 리스트류 컨테이너

• appendleft(x)   데크의 오른쪽에 x를 추가합니다.
• appendleft(x) 데크의 왼쪽에 x를 추가합니다.

이런 식으로 양쪽으로 추가 또는 삭제 할 수 있다. 

 

import heapq


def solution(jobs_input):
    run_time = 0
    time = 0
    working = False
    jobs_input.sort()
    jobs = []
    # job 는 heap 정렬을 위해 [작업의 소요시간, 작업이 요청되는 시점] 로 순서 바꿈
    for job in jobs_input:
        jobs.append([job[1], job[0]])

    job_heap = []
    heapq.heapify(job_heap)
    current_job = []
    time_consume = []
    while True:
        if not working:
            # 대기열에 있는 작업 수행
            if job_heap:
                current_job = heapq.heappop(job_heap)
                working = True
            # 대기열에 아무것도 없는 경우
            elif jobs:
                current_job = jobs.pop(0)
                working = True
            else:
                break
            # fastforward
            if current_job[1] > time:
                time = current_job[1]
        if working:
            # 작업을 완료한 경우 
            if current_job[0] == run_time:
                working = False
                time_consume.append(time - current_job[1])
                run_time = 0
                continue
            # 작업중일 때 대기열에 작업 넣는 일
            else:
                for job in jobs[:]:
                    if job[1] <= time:
                        jobs.remove(job)
                        heapq.heappush(job_heap, job)
        run_time += 1
        time += 1
    return sum(time_consume) // len(time_consume)