[JAVA] Lv3. 디스크 컨트롤러 - 프로그래머스

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

프로그래머스

---

풀릴거같은데 안풀려서 애먹은 문제... 문제에 접근하는 방향을 잡는게 어려웠다.

문제 조건

: 요청 시간, 작업 소요 시간이 주어지고 -> 이것을 바탕으로 평균 요구 시간의 최소를 구해야 함

• 요청이 들어왔을 경우, 해당 시간에 대기 중인 여러 프로세스가 있는 경우, 소요 시간이 가장 적은 프로세스부터 처리 해야 함
• 그러므로, 바로 직전 프로세스가 작업이 끝난 후 실행 예정인 프로세스 목록은 다음과 같은 조건을 만족해야 함
  • 현재 대기중인 프로세스 여야 함 (현재 시간 > 요청 시간)
    • 대기 큐가 비어있다면, 현재 시간과 가장 가까운 요구 시간으로 시간 조정 -> 그 프로세스 실행
  • 위 조건을 만족하는 프로세스 중, 가장 소요 시간이 짧은 프로세스를 선택

구현

처음에 while문에서 우선순위 큐를 사용해 구현하되, time을 별도로 관리해주려니 예외처리 할 것 도 많고 고려해야 할 상황이 많아 자꾸 오답이 나왔다.. 결국 for문으로 바꿔 time을 +1씩 자동으로 해주니 통과

• 주어진 프로세스들이 정렬되지 않았을 경우를 생각해 정렬용 우선순위 큐 구현함 (list)
  • 1순위를 요구 시간, 2순위를 소요 시간(요구 시간 같을 경우 고려)으로 해 오름차순 정렬함
• 요구 시간에 맞춰 프로세스를 넣고 대기시킬 (우선순위)큐 구현(waitQ) : 소요 시간 기준 오름차순
  • 대기하고 있는 프로세스 중 가장 짧은 프로세스부터 실행해야 하므로

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        //주어진 프로세스 요구시간 기준 오름차순 정렬할 큐
        PriorityQueue<Process> list = new PriorityQueue<>(new Comparator<Process>() {
            @Override
            public int compare(Process o1, Process o2) {
                if (o1.sTime == o2.sTime) return o1.rTime - o2.rTime;
                return o1.sTime - o2.sTime;
            }
        });
        //요구 시간 된 프로세스들 대기시킬 큐(소요 시간 기준 내림차순)
        PriorityQueue<Process> waitQ = new PriorityQueue<>(new Comparator<Process>() {
            @Override
            public int compare(Process o1, Process o2) {
                if (o1.rTime == o2.rTime) return o1.sTime - o2.sTime;
                return o1.rTime - o2.rTime;
            }
        });
        
        for (int i = 0; i < jobs.length; i++) {
            list.add(new Process(jobs[i][0], jobs[i][1]));
        }
        
        int answer = 0;
        
        for (int now = 0; now < Integer.MAX_VALUE; now++) { //시간 자동 흐름
            //현재 시간(now) 에 맞춰 가능한 프로세스가 있다면 대기큐에 넣기
            setWaitQ(list, waitQ, now);
            while (!waitQ.isEmpty()){
                Process p = waitQ.poll();
                now += p.rTime; //프로세스 실행 후 완료 시간으로 갱신
                answer += (now - p.sTime); //종료 - 요청 시간 계산
                setWaitQ(list, waitQ, now); //실행 후 시간 기준으로 다시 프로세스 대기큐에 세팅
            }
            if(list.isEmpty() && waitQ.isEmpty()) break;
        }
        return answer / jobs.length;
    }
    private void setWaitQ(PriorityQueue<Process> list, PriorityQueue<Process> waitQ, int i){
        while (!list.isEmpty() && list.peek().sTime <= i){
                waitQ.add(list.poll());
            }
    }

    private class Process {
        int sTime;
        int rTime;

        public Process(int s, int r) {
            this.sTime = s;
            this.rTime = r;
        }
    }
}