Table of contents

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

이 문제는 라면 공장과 비슷한 문제다. 디스크의 요청시작시점과 처리소요시간이 주어졌을 때, 각 작업의 요청시작시점부터 종료까지 걸린 시간의 최소 평균값을 찾는 문제이다.

한 번에 하나의 요청만 수행할 수 있기 떄문에 각 작업은 이전 작업이 끝날 때 까지 기다려야 한다.

위 그림은 하나의 예시일 뿐, A -> B -> C 순서가 아닌 A -> C -> B와 같은 다른 순서로 처리할 수도 있다.

첫번째 풀이

public int solution(int[][] jobs) {
    PriorityQueue<Job> pq = new PriorityQueue<>(Comparator.comparingInt(value -> value.processTime));
    List<Job> list = new ArrayList<>();

    for (int i = 0; i < jobs.length; i++) {
        pq.add(new Job(jobs[i][0], jobs[i][1]));
    }

    for (int i = 0; i < jobs.length; i++) {
        list.add(pq.poll());
    }

    int time = 0;
    int sum = 0;
    while (list.size() > 0) {
        for (int i = 0; i < list.size(); i++) {
            // 시작시간이 현재 시간보다 이전이라면 시작 가능
            if (list.get(i).startTime >= time) {
                // 현재 시간(n) = 현재 시간(n - 1) + 현재 작업의 처리시간
                // 요청부터 처리완료까지 소요시간(n) = 현재 시간(n) - 요청 시작 시간
                time += list.get(i).processTime;
                sum += time - list.get(i).startTime;
                list.remove(i);
                break;
            }
            if (i == list.size() - 1) time++;
        }
    }

    int answer = (sum/jobs.length);
    return answer;
}

class Job {
    int startTime;
    int processTime;

    public Job(int startTime, int processTime) {
        this.startTime = startTime;
        this.processTime = processTime;
    }
}

우선순위 큐를 사용한다. 처리시간이 가장 짧은 디스크부터 처리하면 최소 평균값을 쉽게 구할 수 있다.

주의해야 할 점은 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리해야 한다는 것이다. 현재시간이 2초인데, 처리시간이 1초면서 요청가능 시간이 3초라면 해당 작업은 처리할 수 없다. 요청가능 시간이 2초 이내인 다른 디스크를 찾아야 한다.

for (int i = 0; i < list.size(); i++) {
    // 시작시간이 현재 시간보다 이전이라면 시작 가능
    if (list.get(i).startTime >= time) {
        time += list.get(i).processTime;
        sum += time - list.get(i).startTime;
        list.remove(i);
        break;
    }
    if (i == list.size() - 1) time++;
}

리스트를 탐색하면서 작업 요청을 처리할 수 있는 요소를 검색한다. 리스트의 마지막까지 탐색했지만, 작업 요청을 처리할 수 있는 요소를 검색할 수 없다면 현재 시간을 1초 증가시킨다.

assertThat(solution(new int[][] {
    {0, 3}, {1, 9}, {2, 6}
})).isEqualTo(9);

assertThat(solution(new int[][] {
    {0, 9}, {0, 4}, {0, 5}, {0, 7}, {0, 3}
})).isEqualTo(13);

assertThat(solution(new int[][] {
    {0, 9}, {13, 1}
})).isEqualTo(5);

크게 세가지 경우를 테스트 해봤다.

  • 유휴시간이 존재하지 않고 연속적으로 모든 작업이 처리되는 경우
  • 모든 작업의 요청시간이 같은 경우
  • 작업처리 중간에 유휴시간이 존재하는 경우

두번째 풀이

첫번째 풀이는 우선순위 큐를 사용하긴 하는데 정렬을 위한 용도로만 사용하고 있다. 큐를 이용해서 검색한 요소를 삭제하기가 복잡하기 때문이다. 이번에는 List만 사용한 풀이를 살펴보자.

private int solution(int[][] jobs) {
    List<Disk> list = new ArrayList<>();
    for (int[] job : jobs) {
        list.add(new Disk(job[0], job[1]));
    }
    list.sort(Comparator.comparingInt(disk -> disk.processTime));

    int time = 0;
    int sum = 0;

    while (!list.isEmpty()) {
        for (int i = 0; i < list.size(); i++) {
            if (time >= list.get(i).requestTime) {
                time += list.get(i).processTime;
                sum += time - list.get(i).requestTime;
                list.remove(i);
                break;
            }

            if (i == list.size() - 1) time++;
        }
    }

    return sum / jobs.length;
}

단순히 List를 정렬하고 같은 로직을 수행하기만 하면 된다.

세번째 풀이

반대로 우선순위 큐만 사용할 수도 있다. 그러나 큐에 관련된 연산을 사용하지 않기 때문에 큐를 사용하는 의미가 없다.

private int solution2(int[][] jobs) {
    Queue<Disk> queue = new PriorityQueue<>(Comparator.comparingInt(disk -> disk.processTime));

    for (int i = 0; i < jobs.length; i++) {
        Disk disk = new Disk(jobs[i][0], jobs[i][1]);
        queue.add(disk);
    }

    int time = 0;
    int sum = 0;
    while (!queue.isEmpty()) {
        Disk shouldRemove = null;
        for (Disk disk : queue) {
            if (disk.requestTime <= time) {
                time += disk.processTime;
                sum += time - disk.requestTime;
                shouldRemove = disk;
                break;
            }
        }
        if (shouldRemove != null) {
            queue.remove(shouldRemove);
        } else {
            time++;
        }
    }

    return sum / jobs.length;
}