[프로그래머스 | Java Lv.3] 디스크 컨트롤러 ☠️

문제

 

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

프로그래머스

 

 

☠️☠️☠️ 어렵다 이게 고작 레벨2? 3이네

---

접근

 

제한 사항에 입력값의 요청이 순서대로 주어진다는 말이 없다. 또, 같은 시각에 요청이 여러 개 들어올 수도 있다는 말도 없다. 

따라서 주어진 jobs 배열을 요청 시간대로 정렬하되, 처리 시간에 따라 또 정렬되어야 하지 않을까

 

요청이 모두 처리됐으면 -> 이제 처리 될 수 있는 요청 중에 처리 시간이 가장 짧은 걸 실행

 

이렇게 하기 위해서는 요청 시각에 따라 정렬된 배열과 요청 시각&처리 시각으로 정렬된 배열이 각각 필요하다. 

 

Comparable 

https://velog.io/@llocr/Java-Priority-Queue%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-%EC%99%80-Comparable-Comparator

Java | Priority Queue(우선순위 큐) 와 Comparable, Comparator

        //요청 시각&처리 시간으로 정렬
        PriorityQueue<int[]> pq = new PriorityQueue(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) {
                    return o1[1] - o1[1];
                }
                else return o1[0] - o2[0];
            }
        });

 

첫 번째 제출 - 실패

package week2.baek.heap;

import java.util.*;

public class Ex2 {
    public int solution(int[][] jobs) {
        ArrayList<Integer> list = new ArrayList<>();

        //요청 시각으로 정렬
        Arrays.sort(jobs, ((o1, o2) -> o1[0] - o2[0]));

        for(int[] i : jobs){
            System.out.println(i[0] + ", " + i[1]);
        }


//        //요청 시각&처리 시간으로 정렬
//        PriorityQueue<int[]> pq = new PriorityQueue(new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                if(o1[0] == o2[0]) {
//                    return o1[1] - o1[1];
//                }
//                else return o1[0] - o2[0];
//            }
//        });

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->o1[1]-o2[1]);

//        for(int[] i : jobs){
//            pq.offer(i);
//        }

//        while (!pq.isEmpty()) {
//            int[] j = pq.poll();
//            System.out.println(j[0] + ", " + j[1] + "\n");
//        }

        int count = jobs[0][1];
        list.add(jobs[0][1]);
        int idx=1;

        while(list.size() < jobs.length){
            while(idx < jobs.length && count > jobs[idx][0]){
                pq.offer(jobs[idx]);
                idx++;
            }

            int[] i = pq.poll();
            count += i[1];
            System.out.println(count);
            list.add(count - i[0]);
        }

//        System.out.println(list);

        int avg = 0;
        for(int i : list){
            avg += i;
        }

        return avg/list.size();
    }
}

class Ex2Main{
    public static void main(String[] args) {
        Ex2 ex2 = new Ex2();
//        int[][] jobs = {{0, 3}, {5,5},{5,3},{1, 9}, {2, 6}};
        int[][] jobs = {{0, 3}, {1, 9}, {2, 6}};
        System.out.println(ex2.solution(jobs));
    }
}

 

다수의 테스트 코드에 실패했다. 

 

1. pq가 비어있고, 이후 처리되어야 하는 작업이 있는 데 아직 들어오지 않은 상태를 빼먹은 것

 

2. count >= jobs[idx][0] 에서 등호 빼먹음

 

3. 가장 먼저 요청이 들어온 것부터 실행하게 했는데 이게 원인이었음

 

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        ArrayList<Integer> list = new ArrayList<>();

        //요청 시각으로 정렬
        Arrays.sort(jobs, ((o1, o2) -> o1[0] - o2[0]));

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);

        int count = 0;
        int idx=0;

        while(list.size() < jobs.length){
            while(idx < jobs.length && count >= jobs[idx][0]){
                pq.offer(jobs[idx]);
                idx++;
            }

            //pq가 비어있고, 아직 처리되어야 하는 요청이 남아있지만 들어오지 않은 상태
            if(pq.isEmpty()){
                count = jobs[idx][0];
            }
            else {
                int[] i = pq.poll();
                count += i[1];
                System.out.println(count);
                list.add(count - i[0]);
            }
        }

        int avg = 0;
        for(int i : list){
            avg += i;
        }
         return (int) Math.floor(avg/list.size());
    }
}

---

참고

https://codevang.tistory.com/316

프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA)