[프로그래머스 / 힙] 디스크 컨트롤러 (java)

[1차 코드] - 실패

import java.util.*;
class Solution {
    static class Job implements Comparable<Job>{
        int index; // 작업이 요청되는 시간
        int work; // 작업의 소요시간
        
        public Job(int index, int work){
            this.index = index;
            this.work = work;
        }
        
        @Override
        public int compareTo(Job target){
            return this.work >= this.work ? 1 : -1;
        }// work 소요 시간이 적을수록 우선순위 높다.?
    }
    public int solution(int[][] jobs) {
        int answer = 0;
        PriorityQueue<Job> pq = new PriorityQueue<Job>();
        
        for(int[] job : jobs){
            pq.offer(new Job(job[0], job[1]));
        }
        
        int time = 0;
        for(Job j : pq){
            time += j.work - j.index;
            answer += time;
        }
        answer /= pq.size();
        return answer;
    }
}

[문제점]

 

[2차코드 - 실패]

import java.util.*;
class Solution {
    static class Job implements Comparable<Job>{
        int index; // 작업이 요청되는 시간
        int work; // 작업의 소요시간
        
        public Job(int index, int work){
            this.index = index;
            this.work = work;
        }
        
        @Override
        public int compareTo(Job target){
            if(this.work < this.work) return -1;
            else if(this.work == this.work) {
                if(this.index < this.index) return -1;
                else return 1;
            } else return 1;
        }// work 소요 시간이 적을수록  + 시작 시간이 앞일수록 우선순위
    }
    public int solution(int[][] jobs) {
        int answer = 0;
        PriorityQueue<Job> pq = new PriorityQueue<Job>();
        
        // 우선순위에 따라 job 정렬함.
        for(int[] job : jobs){
            pq.offer(new Job(job[0], job[1]));
        }
        
        int time = 0;
        int current = 0;
        int size = pq.size();
        while(!pq.isEmpty()){
            Job j = pq.peek();
            if(current >= j.index){
                current += j.work;
                time += current - j.index;
                pq.poll();
            }
            else
                current++;
        }
        time /= size;
        return time;
    }
}

[문제점]

compareTo 메소드에서 this와 this를 비교하는게 아니라 target이랑 비교해야 된다!!! 바부

이제 그래도 우선순위큐에서 우선순위를 직접 지정하는 방법에 대해 익히게 되었다. 

 

 

[성공코드]

import java.util.*;
class Solution {
    static class Job implements Comparable<Job>{
        int index; // 작업이 요청되는 시간
        int work; // 작업의 소요시간
        
        public Job(int index, int work){
            this.index = index;
            this.work = work;
        }
        
        @Override
        public int compareTo(Job target){
            if(this.work < target.work) return -1;
            else if(this.work == target.work) {
                if(this.index < target.index) return -1;
                else return 1;
            } else return 1;
        }// work 소요 시간이 적을수록  + 시작 시간이 앞일수록 우선순위
    }
    public int solution(int[][] jobs) {
        int answer = 0;
        PriorityQueue<Job> pq = new PriorityQueue<Job>();
        
        // 우선순위에 따라 job 정렬함.
        for(int[] job : jobs){
            pq.offer(new Job(job[0], job[1]));
        }
        
        List<Job> list = new ArrayList<>();
        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(time >= list.get(i).index){
                    time += list.get(i).work;
                    sum += time - list.get(i).index;
                    list.remove(i);
                    break;
                }
                if(i == list.size() - 1) time++;
            }
        }
        answer = sum / jobs.length;
        return answer;
    }
}

이때 우선순위는 전체 우선순위가 아니라 해당시각에서의 우선순위다. 그래서 for문을 돌면서 가능한지 체크해주는것.

우선순위라고 다 되는게 아니라 우선순위는 우선순위로 체크한다는 것이고 되는 거는 별개다. 

그래서 for문 마지막에 if(i == list.size() - 1) time++이 들어가야 한다. 

 

[참고]

https://developerdk.tistory.com/22

[프로그래머스/코딩테스트 고득점 Kit/힙#3] 디스크 컨트롤러 (Java)