[프로그래머스] 디스크 컨트롤러 / Heap / Python 코드

많은 기업에서 코딩테스트를 프로그래머스 툴로 푼다는 말을 들었다. 프로그래머스는 코딩테스느 문제가 다양하지 않아서 백준만 풀었는데, 얼마 남지 않은 방학동안 프로그래머스 문제를 풀기로 결정했다. 코딩테스트 문제로 들어가니 수준에 맞는 문제 추천을 위한 진단 문제 풀기가 가능하길래 들어가봤다. 문제 이름이 재미있어 보이는 걸로 골랐는데 Lv.3 문제였던 답게 헤맨 과정이 있어 푸는데 시간이 좀 걸렸다. 

 

 

문제 설명 

한 번에 하나의 작업만 수행할 수 있는 하드디스크를 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 디스크 컨트롤러를 구현하는 함수를 작성, input은 2차원 배열로, output은 평균 시간을 int형으로 반환하면 된다.

 

 

문제 해결

문제를 쭉 읽어 봤을 땐 그렇게 어려워 보이지 않았다.

첫 번째 고민은 어떤 방법이 평균 수행 시간이 가장 짧을까? 였다. 고려해야할 점은 작업을 수행하고 있지 않을 때 먼저 요청이 들어온 작업부터 처리한다는 것이다. 운영체제 과목에서 공부했던 CPU 스케줄러가 떠올랐고 역시나 잘 기억이 나지 않아서 다시 찾아본 결과 평균 waiting time이 가장 짧은 비선점형 SJF 방식을 이용하면 되겠다 싶었다. 이럴 때 다시 CS 복습하는 거지 뭐.. 즉, 현재 시점에 대기하고 있는 작업 중 소요시간이 가장 짧은 작업을 먼저 처리하면 된다. 

 

 

놓친 점

처음 풀었을 땐 주어진 테스트케이스에 대해서 통과되었는데 제출하니 반 이상이 실패되어서 고민을 좀 했다. 힌트를 찾아보니 처음 들어오는 작업이 time 0에 들어오지 않는 경우도 있다는 것을 생각하지 못했다..

 

 

풀이 코드 1

def solution(jobs):
    time = 0
    answer = []
    waiting = []
    cnt = 0
    
    jobs.sort()

    while(True):
        for i in range(cnt, len(jobs)):
            if jobs[i][0] <= time:
                waiting.append(jobs[i])
                cnt += 1
            else:
                break

        if (waiting):
            waiting.sort(key=lambda x:x[1])
        else:
            time += 1
            continue

        cur = waiting.pop(0)
        time += cur[1]
        answer.append(time - cur[0])
        
        if(len(answer) == len(jobs)):
            break
        
    return int(sum(answer)/len(answer))

 

코드가 좀 길고 쓸데없는 라인도 있는 것 같다.

다른 풀이도 참고하면서 라인을 줄이고 싶었고, 힙으로 풀어보고 싶어서  조금 더 풀어봤다. 

 

 

풀이 코드 2

from heapq import heappush, heappop

def solution(jobs):
    time = 0
    len_jobs = len(jobs)
    answer = []
    waiting = []
    
    jobs.sort()

    while(len(answer) < len_jobs):
        while jobs and jobs[0][0] <= time:
                root = jobs.pop(0)
                heappush(waiting, (root[1], root[0]))

        if (not waiting):
            time += 1
            continue

        cur = heappop(waiting)
        time += cur[0]
        answer.append(time - cur[1])
        
    return int(sum(answer)/len_jobs)

 

풀이 1과 거의 같고 개선된 점은 단지 waiting 배열을 List로 Heap처럼 사용하는 대신 heapq 라이브러리를 사용한 데에 있다. heappush, heappop 메소드 사용 시마다 heap 구조를 유지하기 때문에 따로 정렬하는 라인이 사라져 수행시간이 훨씬 줄어들었다.

 

한창 코태기가 왔었는데 풀기도 어렵지 않고 다른 사람의 코드를 보는 것도 흥미로웠다. 알고리즘 공부의 재미를 조금씩 되찾게 해준 문제였다!