[알고리즘] 프로그래머스 - 디스크 컨트롤러 1부

💡 Introduction
우선 직관적으로 문제 설명에 맞게 코드를 짜본다. 이후 리팩토링을 진행한다.

📢 문제 설명 요약

프로그래머스 레벨 3 문제로, 한 번에 하나의 일만 처리할 수 있는 디스크 컨트롤러에 소요 시간이 다양한 요청들이 각각 다른 시간에 들어올 때, 각 작업을 어떤 순서로 처리해야 요청된 작업들이 평균 대기 시간을 최소로 가질 수 있는지를 구하는 문제이다.

 

🔍 Hint
평균이 최소라는 것은 결국 합이 최소라는 의미이다. 합을 최소화하는 데에 집중해보자.
합이 최소화되기 위해서는 어떻게 해야 할까?

 

우선 디스크 컨트롤러의 동작 원리에 대해서 알 필요가 있다. 디스크 컨트롤러는 두 가지 일을 반복해서 한다:

1. 모든 요청들을 나열
2. 요청 하나를 선택해 처리

이 반복되는 동작들 중 1번 요청 나열 에서 각 요청들별로 현재의 시점에서 요청했을 때 요청 시작 시점 ~ 요청 완료 시점의 시간을 구해 나열한다. 그리고 2번 요청 하나 선택 에서 최소를 먼저 선택하도록 한다.

 

예시

다음과 같은 배열 jobs 가 있다: [[0, 3], [1, 9], [2, 6]]

이 배열에 대해서 위에서 생각해 낸 방법을 사용하면 아래와 같이 동작할 것이다.

 

시작.

 

1번 과정: 

1 - 1. 디스크 컨트롤러의 위치를 pos 이라고 하겠다. 처음 시작 후 pos = 0 이다.

• A 작업: [(시작점) 0, (소요 시간) 3]
  • A 작업의 요청을 처리하면 대기 시간 + 소요 시간 = 0 - 0 + 3 = 3 이다.
• B 작업: [(시작점) 1, (소요 시간) 9]
  • B 작업의 요청을 처리하면 대기 시간 + 소요 시간 = 0 - 1 + 9 = 8 이다. 
• C 작업: [(시작점) 2, (소요 시간) 6]
  • C 작업의 요청을 처리하면 대기 시간 + 소요 시간 = 0 - 2 + 6 = 4 이다.

1 - 2. A 작업을 처리했다. pos = 3 이다. 현재까지 총 처리 시간은 3 이다.

 

📌 Note
물론 첫 과정에서 0에서 시작하는 요청이 있다면 가장 먼저 들어온 요청이기 때문에 처리 시간에 상관없이 시작점이 0인 요청을 처리한다.

 

2번 과정:

...

N번 과정:

 

끝.

 

위에서 상세하게 설명하지는 않았지만, 1번 과정을 진행하고 나서 이후 2번부터 N 번까지의 과정에서도 (N은 물론 jobs 배열 내의 배열의 수이다, 즉 jobs.length 이다.) 1 - 1 과 1 - 2 의 동작을 반복한다. 이를 코드로 옮기면 아래와 같다:

public int totalAboveAll(int[][] jobs) {
    int count = 0;
    int current = 0;

    List<Integer> minIndices = new ArrayList<>();
    int pos = 0;
    int min = 9999;

    int minIdx = -1;

    while (jobs.length > count) { // 소요 시간을 파악하는 반복문으로, 작업의 개수보다 반복 횟수가 적은 한 계속 반복된다. 마지막에는 총 소요 시간이 구해진다.
        for(int i = 0; i < jobs.length; i++) { // 처리를 대기하는 작업들 각각에 대해,
            //TODO: 이미 처리된 작업을 파악에서 제외한다.
            if (minIndices.contains(i)) continue; // 이미 처리한 작업은 확인하지 않는다.

            int duration = pos - jobs[i][0] + jobs[i][1]; // 지금 파악된 처리 까지 대기 시간이 얼마나 되는지 확인하고,
            if (duration < min) { // 대기 시간이 가장 작은 것을 찾는다.
                min = duration;
                minIdx = i; // 대기 시간이 가장 적은 작업의 배열 내에서의 인덱스를 파악한다.
            }
        }
        pos += jobs[minIdx][1]; // 파악된 대기 시간이 가장 짧은 작업을 처리한 이후의 위치로 옮긴다.
        current += min; // 현재까지의 소요 시간을 파악한다.
        count++; // 몇 개의 작업을 처리했는지 센다.
        //TODO: 이미 처리된 작업을 파악에서 제외한다.
        minIndices.add(minIdx);
        min = 99;

    } // 이 반복문을 빠져나오면 처리해야 할 작업들을 모두 current 에 누적해 더한 상태로 빠져나온다.

    return current;
}

 

하지만 여기에는 문제가 있다. 동작을 반복하면서 순서대로 결정을 내릴 것이고, 각 시점의 판단에서만 최소 처리 시간이 걸리는 작업을 선택하므로 각 시점에서의 최소는 총 합을 최소로 만든다는 보장을 하는 것은 아니다. 즉, 각 시점에서 최소를 모두 선택해도 합했을 때 최소가 아닐 수도 있다는 문제가 있다.

 

jobs = [[0, 16],[0, 14],[15, 1],[13, 13]] 일 때,

 

최소 합은 [0,16] -> [15, 1] -> [13, 13] -> [0, 14] 순서대로 처리했을 때의 결과인

16 + 2 + 17 + 44 = 79 이다.

 

하지만 위의 알고리즘은 매번 최소 처리 시간의 요청을 선택하므로

[0, 14]  -> [13, 13] -> [15, 1] -> [0, 16] 순으로 처리해

14 + 14 + 13 + 44 = 85 이다.

 

79 < 85 이므로 위 알고리즘은 최소 합을 찾는데에 실패했다.

 

그렇다면 모든 경우의 수를 확인해봐야하는 것일까?

 

다음 시간에는 어떤 방법을 활용할 수 있는지 알아본다.

 

출처

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

프로그래머스