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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627

 

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

 
제한사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

---

** 현재시간 값을 무조건 +1씩 더해주면서, 완료된 작업을 list에서 제거했는데,,, 소스가 너무 길어지고 지저분해졌다.

** 수행 list를 따로 두지 않고, 즉시 완료했다고 가정하고 소요시간을 현재시간 값에 더하니 소스가 매우 깔끔해진 것 같다. (시간복잡도도 줄어 들었다고 판단된다.)

 

풀이 순서

1.  입력된 jobs을 아래 정렬조건으로 PriorityQueue를 이용해 정렬(PriorityQueue를 굳이 안써도 될듯,,)
   1. 정렬 조건 1) workTime(소요시간)이 짧을수록 앞으로   
   2. 정렬 조건 2) start(요청시간)이 짧을 수록 앞으로
2. 현재시간(var: time)을 반복적으로 +1씩 더해주면서, 수행할 Job이 있는지 확인(time >= list.get(i).start)
3. 수행할 Job은 완탐으로 돌면서 반복시켜주는게 아니라, 즉시 수행했다고 가정하고 현재시간 값에 해당 job의 workTime(소요시간)을 더해준다. 그 즉시, 해당 Job은 List에서 제거해준다.(list 탐색하는 for문에 break가 있어서 문제가 되진 않는다.)

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
 

class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<Job> pq = new PriorityQueue<>();
        List<Job> list = new ArrayList<>();
        
        //Job 정렬
        for (int i = 0; i < jobs.length; i++) {
            pq.add(new Job(jobs[i][0], jobs[i][1]));
        }
        
        //list에 정렬 조건1), 2)를 바탕으로 정렬된 Job 순차적으로 삽입
        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++) {
                // workTime(소요시간)이 짧은 순서부터 조회
                // workTime(소요시간)이 짧으면서, start(요청시간)이 짧은 순서대로 작업
                if (time>=list.get(i).start) {
                  	// 현재시간에 workTime(소요시간)을 더해줌
                    time+=list.get(i).workTime;
                    // 요청부터 종료까지 걸린 시간: 현재시간(time) - start(요청시간)
                    sum+=time-list.get(i).start;
                    list.remove(i);
                    break;
                }
                // 위 조건에 해당되는 작업이 없다면 time+=1
                if (i == list.size()-1) time++;
            }
        }
        
        int answer = (sum/jobs.length);
        return answer;
    }
    static class Job implements Comparable<Job> {
        int start;
        int workTime;

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

        // 정렬 조건 1) workTime(소요시간)이 짧을수록 앞으로
        // 정렬 조건 2) start(요청시간)이 짧을 수록 앞으로
        @Override
        public int compareTo(Job o) {
            if (this.workTime < o.workTime) return -1;
            else if (this.workTime == o.workTime) {
                if (this.start < o.start) return -1;
                else return 1;
            } else return 1;
        }
    }
 
}