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

snusun·2021년 1월 12일
0

정말 어려웠던 문제! 내가 자바에 익숙하지 않다는 것을 실감시켜 준 문제다 ㅎㅎ
새로 익힌 개념이 많아 공부하고 정리해가며 풀었다.

  • 알고리즘
    1. 요청 시간에 대해 오름차순 정렬. 동일한 요청 시간의 경우 작업 시간에 대해 오름차순 정렬
    2. 대기 큐에 넣을 것이 있으면 넣기(작업이 끝나기 전 들어온 요청에 대해)
    3. 대기 큐에 작업이 있으면 그 작업을 수행하고 수행시간 계산, 없으면 job list에서 뽑아서 수행시간 계산
    • 대기 큐는 작업 시간이 짧은 것이 우선인 우선순위 큐이다.

이번에 새로 iterator라는 함수를 사용했는데, 자바의 컬렉션 프레임웍에서 컬렉션에 저장되어 있는 요소들을 읽어오는 표준화된 방법이다.
comparable은 comparator와 비슷하게 정렬 방법을 직접 규정하는 방법이다. Comparable interface를 implements 후, compareTo() 메서드를 오버라이드하여 구현할 수 있다.

import java.util.*;

class Solution {
    static class Disk implements Comparable<Disk>{
        int requestTime;
        int workTime;
        public Disk(int requestTime, int workTime){
            this.requestTime = requestTime;
            this.workTime = workTime;
        }

        @Override
        public int compareTo(Disk d){ //대기 큐에서 작업을 선택할 때 작업시간이 가장 작은 작업부터 수행
            return this.workTime - d.workTime;
        }
    }

    public int solution(int[][] jobs) {
        int answer = 0;
        Arrays.sort(jobs, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]); //배열 sort
        List<Disk> jobList = new ArrayList<>(); // 객체 Disk를 요소로 하는 List 선언
        for (int i=0; i < jobs.length; i++) {
            jobList.add(new Disk(jobs[i][0], jobs[i][1])); // 배열요소들을 Disk 객체의 속성으로 전달
        }

        //작업이 수행 중일 때 요청이 들어오는 작업들을 관리하기 위한 대기 큐. poll하면 작업시간이 짧은 것을 return한다.
        PriorityQueue<Disk> waitingQueue = new PriorityQueue<>();
        int prevTime = 0;
        while(!jobList.isEmpty() || !waitingQueue.isEmpty()){
            //대기 큐에 add
            Iterator<Disk> iter = jobList.iterator();
            while(iter.hasNext()){
                Disk job = iter.next();
                if(job.requestTime > prevTime) break;
                waitingQueue.add(job);
                iter.remove();
            }

            Disk currentJob;
            if(waitingQueue.isEmpty()){ // 작업 후 요청
                currentJob = jobList.remove(0);
                answer += currentJob.workTime;
                prevTime = currentJob.requestTime + currentJob.workTime;
            } else { // 작업 중 요청
                currentJob = waitingQueue.poll();
                answer += prevTime - currentJob.requestTime + currentJob.workTime;
                prevTime += currentJob.workTime;
            }
        }
        return answer/jobs.length;
    }
}

참고: https://velog.io/@sa833591/%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv.3

profile
대학생 근데 이제 컴공을 곁들인

0개의 댓글