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

문제

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

풀이

스케줄링 알고리즘 중 최단 작업 우선 스케줄링(Shortest Job First, SJF)을 구현하는 문제이다. SJF는 운영체제의 스케줄러가 CPU 점유 시간이 가장 짧은 프로세스부터 우선적으로 할당하는 것이다.

SJF는 선점 최단작업 우선 스케줄링 알고리즘과 비선점 최단 작업 우선 스케줄링 알고리즘이 있다.

선점 최단 작업 우선 스케줄링 알고리즘

준비 상태 큐에 도착한 프로세스의 CPU 점유 시간이 실행 중인 프로세스의 CPU 점유 시간보다 더 짧다면 실행 중인 프로세스를 멈추고 CPU 점유 시간이 더 짧은 프로세스를 실행하도록 한다.

비선점 최단 작업 우선 스케줄링 알고리즘

준비 상태 큐에 도착한 프로세스의 CPU 점유 시간이 가장 짧은 순서대로 프로세스를 실행한다. 선점 최단 작업 우선 스케줄링 알고리즘과 다르게 이전 프로세스가 종료되어야 다음 프로세스가 실행 되기에 먼저 도착한 프로세스의 CPU 점유 시간이 길면 나중에 도착한 CPU 점유 시간이 짧은 프로세스는 이전 프로세스의 실행이 끝날 때까지 기다려야 한다.

SJF방식에서 스케줄러는 CPU 작업 소요 시간을 예상해야 하는 어려움이 있다. 또한 점유 시간이 짧은 프로세스 먼저 실행되기 때문에 점유 시간이 긴 프로세스는 실행되지 못할 수도 있다.

디스크 컨트롤러 문제는 실행 중인 프로세스가 종료되면 다음의 프로세스가 실행되므로 비선점 최단 작업 우선 스케줄링 방식이다. 현재 진행중인 작업이 종료되기 이전에 요청이 온 작업이 있다면 해당 작업의 요청 시간과는 상관없이 실행 시간이 짧은 순서대로 먼저 실행하면 된다.

javascript의 배열의 sort 메소드를 이용하면 우선순위 큐를 구현하여 문제를 풀 수 있지만 문제가 heap 카테고리에 있으니 heap을 이용해 문제를 풀어보려고 한다.

1. 프로세서의 현재 시간을 담을 변수 time을 선언한다. 또한 계산의 편의를 위해 모든 작업의 요청 시간에서 가장 먼저 들어온 작업의 요청 시간을 빼 time 변수를 0으로 초기화 한다.
2. 작업 대기열을 담을 최소heap을 만든다. jobs 배열의 작업 중 요청 시간이 가장 빠른 작업들을 꺼내 대기열 heap에 추가해 준다.
3. 대기열 heap에서 루트 노드의 작업을 꺼내 실행시킨다. 그리고 해당 작업이 종료된 시간을 time 변수에 더해준다.
4. 작업 대기열 jobs 배열에서 현재 time과 같거나 일찍 들어온 요청이 있다면 해당 작업을 대기열 heap에 추가해준다. 없다면 jobs의 작업 중 요청 시간이 가장 빠른 작업 들을 대기열 heap 에 추가해준다.
5. heap과 job의 작업 개수가 0이 될 때까지 3 – 4번 항목을 반복한다.

이때 중요한 건 작업을 실행시키고 새로운 작업을 heap에 추가하면서 매번 heap을 정렬하는 과정이 필요하다는 것이다.

먼저 작업 대기열을 담을 heap을 만들어 보자.

Heap 클래스를 생성하였다. jobs 배열 아이템을 작업 소요 시간 기준으로 최소힙을 생성하기에 노드[1] 값을 비교해주며 bubbleDown, bubbleUp 정렬을 진행해 준다.

Heap에 노드가 추가되고 삭제될 때 bubbleUp, bubbleDown 방식으로 정렬하는데 이 때 시간복잡도는 O(logN)이다.

이제 heap을 활용하여 solution 함수를 만든다.

전체 코드

직접 heap을 구현하여 푸는 것이 코드가 훨씬 길어졌지만 heap을 직접 구현하고 공부하는데 도움이 되었다.

잘하자!