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

문제 링크

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

코딩테스트 연습 - 디스크 컨트롤러

문제를 아주 잘 읽어봐야 한다. (그렇지 않으면 무수한 테스트케이스 실패의 환대를 받을 것임 ㅎ)

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

여기서 주의해야할 점은 "요청부터 종료까지 걸린 시간"의 평균을 구하는 것이다. 작업시간이 아무리 빠르더라도 요청한 시점에서 한참 지난 다음 작업을 수행한다면 평균 소요시간은 올라갈 수밖에 없다.

 

또한 jobs를 보면 그 어디에도 "작업 요청 시점이 순서대로"들어온다는 가정이 없다. 따라서 예시만 보고 "알아서 요청시점 순으로 들어오겠지?"와 같은 안일한 생각은 하면 안된다.

 

따라서 나의 로직은 이렇게 나뉜다.

1. 들어온 jobs를 작업 요청 시점순으로 정렬한다. (만약 시점이 같은 변수가 여러개 있다면, 직업 소요시간이 적은 것을 우선순위로 둔다.)

2. 해당 jobs를 우선순위큐에 담는다. 기준은 작업 소요시간이 적은 것(같으면 요청 시간이 빠른 순), 타입은 직접 정의한 객체 [Job] 

   

class Job implements Comparable<Job> {

        private int start;
        private int work;

        public Job(int start, int work) {
            this.start = start;
            this.work = work;
        }

        public int getStart() {
            return this.start;
        }

        public int getWork() {
            return this.work;
        }

        @Override
        public int compareTo(Job job) {

            if (this.work > job.getWork())
                return 1;
            else if (this.work < job.getWork())
                return -1;
            return 0;
        }
    }

 

3. 큐에 저장된 값을 뺀다.(가장 소요시간이 빠른 작업이 나오게 된다.) 
     3-1. 작업 요청 시간이 현재 시간보다 늦을 경우 (작업을 바로 진행할 수 없는 경우)

            해당 작업을 temp에 저장해두고, 큐에서 다음 루트 노드를 꺼내 작업 요청 시간과 현재 시간을 비교해서 유효한 시간이 나올때까지              작업을 계속 뽑는다. (유효하지 않은 작업은 계속 temp 우선순위 큐에 넣어둔다)

            유효한 작업이 나오면 총 걸린 작업시간을 answer 에 합산해준다.
            [총 걸린 작업시간] : [작업 소요시간] + [현재 시간 - 요청 시간 (요청된 시점 이후로 대기한 시간)]
            temp에 빼놨던 작업들을 다시 기존 큐에 집어넣는다.

     3-2. 작업 요청 시간이 현재 시간보다 이전일 경우 (작업을 바로 진행할 수 있음)

            총 걸린 작업시간을 answer 에 합산해준다.
            [총 걸린 작업시간] : [작업 소요시간] + [현재 시간 - 요청 시간 (요청된 시점 이후로 대기한 시간)]

4. 현재 시간을 1초 올려준다. (3-1에서 모든 작업 요청 시간이 현재 시간보다 늦을 경우, 아무런 일 없이 4번으로 넘어간다.)

5. 모든 작업이 수행 될 때까지 3번, 4번을 반복한 후, 평균 작업시간을 반환한다.
    [평균 작업시간] : 작업시간 합산된 answer / 총 작업 수

 

 

로직을 수행하는덴 오래 걸리지 않았지만, 4번 과정의 문제로 한동안 테스트케이스 11번을 통과하지 못해 헤맸었다.

처음엔 작업시간을 1초 올려주는게 아니라, 큐에 있는 루트 노드의 작업 요청시간을 찾아 시간을 해당 시점으로 바로 땡겨주었었다.

만약 케이스가 [[10, 10], [30, 10], [50, 2], [51, 2]] 이 경우라면?
10, 10 다음 30초대 시간에 작업을 해야 하는데, 우선순위 큐에서 빼면 50, 2가 빠져 시간을 50초로 밀어버리기 때문에 30, 10 이 실행이 안됨. 

소요 시간을 줄이려고 한게 화근이 되어버림... 1초씩 차근차근 올려주니 통과했다 ㅠㅠ

 

import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Comparator;
class Solution {
    class Job implements Comparable<Job> {

        private int start;
        private int work;

        public Job(int start, int work) {
            this.start = start;
            this.work = work;
        }

        public int getStart() {
            return this.start;
        }

        public int getWork() {
            return this.work;
        }

        @Override
        public int compareTo(Job job) {

            if (this.work > job.getWork())
                return 1;
            else if (this.work < job.getWork())
                return -1;
            return 0;
        }
    }
    public int solution(int[][] jobs) {
        int answer = 0;
        int time;
        PriorityQueue<Job> que = new PriorityQueue<>();
        PriorityQueue<Job> temp = new PriorityQueue<>();
        
        Arrays.sort(jobs, new Comparator<int[]>() {
            @Override public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) {
                    return o1[1] - o2[1]; 
                }else { 
                    return o1[0] - o2[0]; 
                } 
            } 
        });
        for (int i = 1; i < jobs.length; i++) {
            que.add(new Job(jobs[i][0], jobs[i][1]));
        }
        answer = (jobs[0][0] + jobs[0][1]) - jobs[0][0]; 
        time = (jobs[0][0] + jobs[0][1]);
        while(que.size() != 0) {
            Job j = que.poll();
            if (j.getStart() <= time) {
                answer += j.getWork() + (time - j.getStart()); // 대기하다 작업 시작해서 완료한 총 시간
                time += j.getWork();
            }
            else {
                if (que.size() == 0) {
                    temp.add(j);
                }
                while(que.size() != 0) {
                    temp.add(j);
                    j = que.poll();
                    if (j.getStart() <= time) {
                        answer += j.getWork() + (time - j.getStart()); 
                        time += j.getWork();
                        break;
                    }
                    if (que.size() == 0)
                        temp.add(j);
                }
                if (que.size() == 0)
                    time++;//temp.peek().getStart();
                while(temp.size() != 0)
                    que.add(temp.poll());
            }
        }
        return answer / jobs.length;
    }
}

시간 순 작업을 할때, 정확한 근거 없이는 함부로 시간을 앞당기지 말것..