[프로그래머스] 디스크컨트롤러(Java, Level.3)

문제

 

작업이 요청되는 시점과 소요시간을 담은 2차원 배열이 주어진다. 

작업의 요청부터 종료까지 걸린 시간의 평균에 대한 최소값을 구하는 Soluntion 함수 구현 

(소수점 이하의 수는 버림)

 

입출력의 예 

 

 

풀이

요청시간과 소요시간이 주어진다.

 

종료까지의 최솟값을 구하기때문에 빨리끝나는것부터 진행하면 된다구 생각했다. 

나는 요청시간+소요시간의 값이 가장 작은것부터 진행을 하고 만약 같을 경우,

요청시간이 더 짧은 것을 우선으로 진행한다! 라고 생각했다. 

 

그런 생각은 했지만 구현하는 것은 어려워 여러 블로그을 참고하였다. 

내 생각과 원리는 비슷했으나 요청과 소요시간에 대해서 각자 오름차순으로 정렬을 해야 했다.

해당 방식으로 구현하는 것이 더 간단하고 예외상황에 대한 처리가 없을 것 같다는 생각이 들었다. 

 

그러면 이제 코드에 대한 풀이해보겠다. 

크게 4가지 단계로 나뉜다. 

1. 변수 설정

2. 현재 작업이 완료되는 시점까지 들어온 모든 요청을 큐에 저장

3. 요청시간이 끝난 업무의 수행시간 확인하기

4. 평균값 반환 

 

 

1. 변수 설정

 

total : 반환할 값

count : 현재 업무가 종료된 개수 

index : 현재 요청시간이 완료된 업무의 개수 

endTime : 현재 시점 

 

jobs : 요청시간에 따른 오름차순

PriorityQueue : 소요시간에 따른 오름차순 정렬 & 업무를 수행하면서 업무 순서를 정해줌 

---

[ comparator 인터페이스 ]

comparator 인터페이스를 통한 오름차순이다. 

내가 이해한 내용을 정리해놨다. 

 

comparator 인터페이스는 시용자가 원하는 복잡한 정렬을 할 수 있도록 도와준다. 

람다식을 통해서 오름차순, 내림차순을 정렬할 수 있다. 

 

(o1, o2) -> o1[0] - o2[0]

양수일 경우에만 두 원소 자리 변경

 

예시 : [[0,1], [1, 3]]

 

1. (o1, o2) -> o1[0] - o2[0] -> 오름차순

([0,1], [1, 3]) -> 0 - 1

  => [[0,1], [1, 3]]

 

2. (o1, o2) -> o2[0] - o1[0] -> 내림차순

([0,1], [1, 3]) -> 1 - 0

  => [[1, 3], [0,1]]

 

[참고]

https://lotuus.tistory.com/35

자바 배열, 객체 정렬하기 : Comparable, Comparator 인터페이스 (+다중정렬 예시)

---

while문 안에 2,3단계가 포함되어 있다. 

while문은 count가 주어진 업무의 개수보다 적을 경우에만 진행한다. 

이뜻은 모든 업무가 수행될 때 동안만 진행하겠다는 뜻이다. 

for문이 아닌 while문을 사용한 이유는 3단계에서 알 수 있다. 

 

2. 현재 작업이 완료되는 시점까지 들어온 모든 요청을 큐에 저장

while에 2가지 조건이 있다. 

1. 현재 수행 중인 업무 번호 < 업무의 개수

2. 현재 수행 중인 업무의 요청 시간 <= 현재 시점

 

1번 조건을 통해 arrayindexoutofboundsexception 예외 발생 방지한다.

2번 조건을 통해 현재 업무의 요청시간이 현재 흐른 시점보다 작거나 같은지 확인한다. 

이 2조건을 만족할 경우에만 PriorityQueue에 업무 배열을 저장한다. 

즉, 요청시간이 끝난 업무에 대해서만 해당 큐에 저장한다. 

 

while문을 통해 현재시점보다 요청시간이 작거나 같은 작업을 큐에 저장한다.

즉, 1개 이상의 작업이 큐에 저장될 수 있다는 의미이다. 

하지만 PriorityQueue에 저장하기에 2개 이상의 작업(배열)을 가지고 있어도 2번째 원소인 소요시간에 따라 오름차순 정렬이 된다. 

 

만약 해당 조건을 만족하지 못하는 경우 3단계로 이동한다. 

 

 

3. 요청시간이 끝난 업무의 수행시간 확인하기

 

3단계는 PriorityQueue가 비어있을 경우와 그렇지 않은 경우로 나뉜다. 

PriorityQueue는 요청시간이 끝난 업무를 의미한다. 

그러면 요청시간이 끝난 업무가 있을 경우와 없을 경우에 따라 살펴보겠다. 

 

1. 요청시간이 끝난 업무 O

먼저 else 부분부터 살펴보겠다. 

 

PriorityQueue의 원소 하나를 가져온다.

total에는 기존 total에 해당 원소의 종료까지의 시간을 더한다. 

endTime은 현재시점인 endTime에 해당 원소의 소요시간을 더한다. 

count를 1를 더하여 하나의 업무가 종료되었음을 알린다. 

 

2. 요청시간이 끝난 업무 X

그 다음 if부분이다. 

처음에는 endTime = jobs[index][0]; 이 아닌 endTime = jobs[0][0]; 라고 생각하였다. 

하지만 해당 생각은 틀렸다.

무조건 jobs의 첫번째 요소가 아닌 현재 수행해야 하는 요청시간이 필요로 한다는 것을 깨달았다. 

해당 부분은 예시와 함께 아래 그림과 함께 풀이하겠다. 

 

예시 : { { 4, 5 }, { 30, 2 }, { 4, 6 },  { 100, 1 } }

예시 jobs는 1단계에 의해 { { 4, 5 }, { 4, 6 }, { 30, 2 }, { 100, 1 } }로 오름차순 정렬이 된다. 

 

요청시간이 4인 { 4, 5 }, { 4, 6 }은 업무가 완료되었다. 

현재 시점인 endTime은 15이며 total은 5 + 11 = 16이다. 

 

jobs의 3번째 원소인 { 30, 2 }가 수행될 차례지만 15인 endTime이 30에 도달하지 못했다. 

따라서 endTime은 30으로 설정된다. 여기서 endTime = jobs[0][0];가 아닌 endTime = jobs[index][0];을 사용해야 한다는 점을 알 수 있다. 

 

4번째 원소인 { 100, 1 }도 동일하다. 

 

4. 평균값 반환 

 

2, 3단계를 거친 total를 jobs의 개수만큼 나눠 평균을 구한다. 

소수점을 버리라고 하였으니 int형으로 변환하여 반환한다. 

 

코드 

import java.util.*;

 

public int s7(int[][] jobs) {

        // 1. 변수 설정

        int total = 0; // 결과값

        int count = 0; // 주어진 모든 일을 완료했는지

        int index = 0; // 현재 진행중인 일의 번호

        int endTime = 0; // 현재 시점

        // 오름차순

        // 가장 작은 수부터 업무 진행 시작함.

        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); // 0번째 오름차순

        PriorityQueue<int[]> jobsPriorityQueue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); // 1번째 오름차순

        

        while (count < jobs.length) {

            while (index < jobs.length && jobs[index][0] <= endTime) {

                // 1. 현재 인덱스번호가 jobs 배열에 해당하는지

                // 2. 현재 인덱스 업무의 대기시간이 다 지났는지

                jobsPriorityQueue.add(jobs[index]);

                index++;

            }

            // jobsPriorityQueue 초기화

            if (jobsPriorityQueue.isEmpty()) {

                // 비어 있는 경우

                endTime = jobs[index][0];

            } else {

                //

                int[] temp = jobsPriorityQueue.poll();

                total += endTime + temp[1] - temp[0];

                endTime += temp[1];

                count++;

            }

        }

        return (int) total / jobs.length;

    }

 

 

프로그래머스 문제

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

프로그래머스