[JavaScript] 프로그래머스 코딩테스트 레벨 3 : 디스크 컨트롤러

📌  문제

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

 

예를 들어

- 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 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

---

📌  풀이

이해하기

• 초기 작업을 위해 작업이 요청되는 시점 기준으로 정렬
• 예를 들어 jobs = [[0, 3], [1, 9], [2, 6]] 일 때 1번째 작업을 수행하고 나면 3초가 되어 있다. 2번째, 3번째 작업 모두 3초 전에 요청 되어 있다. 1번째 작업이 끝나고 나면 두 작업 중 하나가 수행되어야 하는데, 작업이 요청되는 시점 기준으로 진행(현재 정렬)하면 예시처럼 오답이 발생한다. 어떤 작업이 끝나는 시간 내에 작업이 요청된 작업들이 있다면, 그 작업들은 작업의 소요시간 기준으로 정렬해 처리해야 한다.
• 작업의 요청 시간과 작업의 수행 시간의 합을 계산할 waitingTime, jobs를 순회할 idx, 작업이 완료된 현재 시간을 카운트할 currentTime을 0으로 초기화 해 시작한다.
• 만약 현재 시간 이전에 요청된 작업도 없고, 큐에도 작업이 없다면 현재 시간을 다음 작업의 요청 시점으로 넘긴다. 그래야 다음 작업을 기준으로 진행할 수 있기 때문이다. 큐에 작업이 없는 거지 idx가 length만큼 가지 않는 한 아직 해야 할 직업이 남아 있다. 아무 생각 없이 이 부분을 안 썼다가 예제는 통과했으나 출력 크기 초과가 났다. ([[0, 1], [2, 2], [2, 3]]의 경우가 그랬다. 현재 시간이 1초가 되었는데 1번째 작업은 종료되었고 큐에는 들어 있는 게 없었다. 이러면 2번째 작업으로 넘어가야 한다.)

반복문 수행

• 먼저 jobs의 0번째 작업부터 시작한다. jobs의 길이만큼 인덱스가 순회하고, 우선순위 큐에도 남아 있는 작업이 없으면 반복문을 종료하도록 설정한다. 즉 jobs의 길이만큼 인덱스가 순회하지 못하거나, 우선순위 큐에 아직 작업이 남아 있다면 시간이 더 필요하다.
  • jobs = [[0, 3], [1, 9], [2, 6]] 라고 할 때, 반복문과 첫 번째 조건문을 통과한다. 현재 시간 (0) 이전에 들어온 작업은 1번째 작업 밖에 없기 때문에 continue는 끝이 나고, idx는 1 증가한 상태로 큐에는 [0, 3]만 들어 있다. 즉 작업할 것이 있으므로 작업을 진행한다. 1번째 작업이 진행되면 현재 시간은 3초로 바뀌어 있다. waitingTime는 현재 시간에서 작업의 요청 시간을 뺀 값으로, 작업이 대기한 시간을 의미한다. 즉 다음 작업은 3초를 대기했다. 큐 안에 있는 작업은 작업이 완료되었기 때문에 삭제된다.
  • waitingTime = 3, idx = 1, currentTime = 3로 다시 시작한다. 4 >= jobs[1][0] 으로 큐에는 [1, 9]가 들어오고 idx는 2가 된다. 이 때 현재 시간 전에 들어온 작업들이 또 없는지 확인해야 하기 때문에 continue로 다시 돌아가보면, [2, 6] 또한 현재 시간인 3초 전에 요청되었기 때문에 큐에 삽입된다. idx는 3이 되고 현재 큐에는 [[1, 9], [2, 6]]이 들어 있다.
    • 이 때, 위에서 말한 것처럼 큐에서는 작업의 요청시간이 중요한 게 아니라 작업의 소요 시간이 중요하다. 이미 처음에 요청 시간 순으로 정렬했고, 요청 시간 안에 들어온 작업들은 빨리 끝나는대로 진행되어야 하기 때문에 sort로 작업의 시간 소요 순으로 재정렬한다. 큐는 [[2, 6], [1, 9]]가 된다.
    • 큐는 비어 있지 않으니(해야 할 작업이 있으니) 큐 안에 있는 작업들을 수행한다. 첫 번째 작업부터 진행하면 currentTime은 3+6으로 9가 됐다. waitingTime은 누적되니 3 + 9 - 2로 10이 된다. 작업이 진행되었으니 삭제한다.
  • 다시 반복문을 돈다. idx가 3이라 jobs.length와 같지만, 두 번째 조건인 큐에 작업이 있기 때문에 while문은 통과된다. 다만 if문에서 false가 되면서 더 이상 큐에 작업을 더하지 않고, 있는 작업을 수행한다. currentTime은 9 += 9 로 18이 되고, waitingTime은 10 + 18 - 1로 27이 된다. 즉 3가지 작업을 다 수행하면 수행 시간과 대기 시간을 모두 더했을 때 27초가 걸린다.
• 이 시간을 jobs.length로 나눠 정수로만 나오도록 parseInt를 하면 된다.

function solution(jobs) { //  jobs = [[0, 3], [1, 9], [2, 6]] 
    let waitingTime = 0;
    let idx = 0;
    let currentTime = 0;
    
    // 요청 시점으로 정렬
    jobs.sort((a, b) => a[0] - b[0])
    
    const priorityQueue = []
    
    // 아직 처리되지 않은 작업이 남아 있거나 우선순위 큐에 대기중인 작업이 있을 경우
    while (idx < jobs.length || priorityQueue.length !== 0) {
        // 아직 처리되지 않은 작업 중 현재 시간 이전에 들어온 작업들을 우선순위 큐에 삽입
        if (jobs.length > idx && currentTime >= jobs[idx][0]) {
            priorityQueue.push(jobs[idx++])
            // 우선순위 큐에서는 작업의 소요 시간 순으로 정렬
            priorityQueue.sort((a, b) => a[1] - b[1])
            continue
        }
        // 우선순위 큐에 대기중인 작업이 있을 경우
        if (priorityQueue.length !== 0) {
            currentTime += priorityQueue[0][1]
            waitingTime += currentTime - priorityQueue[0][0]
            priorityQueue.shift();
        } else {
            currentTime = jobs[idx][0]
        }
    } return parseInt(waitingTime / jobs.length)
}

 

하루 꼬박 고민했는데 도저히 힙을 어떤 식으로 이용해야 할지 몰라서 문제를 풀지 못했다. 

우선순위 큐라는 이름의 배열을 사용해 풀었지만 진짜 힙을 사용한 게 아니라서 주제에 맞는 문제는 아니었던 것 같다. 

그나저나 진짜 풀 게 없는데 큰일이네!

 

[프로그래머스/Javascript] 디스크 컨트롤러 - Kyun2da Blog