문제 링크

풀이

Heap문제라 PriorityQueue를 사용하여 풀었다.
처음에 세가지를 잘 생각해서 문제를 설계하고 풀어나가면 된다.

1. 디스크 컨트롤러는 먼저 들어온 작업 순서대로 처리한다.
2. 그런데 대기 작업 중에서 작업이 완료되는데 걸리는 시간이 가장 작은 작업이 우선적으로 처리한다.
3. 대기큐에 있던 작업 수행과 새 작업은 계산 방법이 조금 다르다.

이 중 앞에 두가지를 이해하지 못해 정말 많이 방황했다. 이를 정리하면,,,
첫번째로, 처음에 [][] jobs 요청시간에 대하여 오른차순 정렬. 단, 요청 시간이 동일한 경우 작업 시간에 따라 오름차순 정렬로 정렬해줘야 한다. 이와 관련해서 문제에서 딱히 힌트가 없었던 것은 아니다.

두번째로, 작업 시간에 대하여 오름차순 정렬되는 대기 큐(PriorityQueue)를 생성해야 한다.

문제에서 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 이라는 힌트가 있는데, 이것을 가지고 앞에 두개를 설계해낼 수 있어야 한다. 개인적으로 알고리즘 문제를 풀 때, 이런 문제가 가장 어렵게 느껴진다...

그리고 대기하고 있던 작업과 새 작업을 구분하여 계산해야 한다. 이 부분을 작성하는데에도 조금 껄끄러웠지만 나름대로 잘 작성했다. 하지만 앞에 두가지가 제대로 되지 않아...(쩜쩜쩜)

1) jobs 위와 같이 정렬!
2) 정렬된 jobs를 jobList에 담는다.
3) 대기큐를 PriorityQueue 만든다.
4-1) 이전 작업의 끝난 시간이 요청 시간보다 작으면 대기큐에 추가!
4-2) 현재 대기큐에 작업이 없으면 그 다음 작업 수행!
5) 대기큐에 있던 작업 수행과 새 작업은 계산 방법이 조금 다르다.
6) 전체 작업 시간/갯수 계산. 끝.

코드

import java.util.*;
class Solution {
    static class Disk implements Comparable<Disk> {
        int requestTime;
        int taskTime;
        public Disk(int requestTime, int taskTime) {
            this.requestTime = requestTime;
            this.taskTime = taskTime;
        }

        @Override
        public int compareTo(Disk o) {
            return this.taskTime - o.taskTime;
        }
    }

    public static int solution(int[][] jobs) {
        int len = jobs.length;

        Arrays.sort(jobs, (o1,o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0] ); // 요청 시간([0])에 대하여 오름차순 정렬( 요청 시간이 동일한 경우, 작업 시간에 따라 오름차순 정렬)
        List<Disk> jobList = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            jobList.add(new Disk(jobs[i][0], jobs[i][1]));
        }

        PriorityQueue<Disk> waitingJob = new PriorityQueue<>(); // 대기 큐
        int prev_end = 0;
        int sum = 0;
        while( !jobList.isEmpty() || !waitingJob.isEmpty() ) {
            boolean isNew = false;

            // 요청 시간이 이전에 끝난 시간보다 더 크면 waiting이 아님.
            Iterator<Disk> iter = jobList.iterator();
            while( iter.hasNext() ) {
                Disk job = iter.next();
                if( job.requestTime > prev_end ) break;

                waitingJob.add(job);
                iter.remove();
            }

            // 대기 요청이 없으면 가장 먼저 들어온 작업 수행!
            if( waitingJob.size() == 0 ) {
                waitingJob.add(jobList.get(0));
                jobList.remove(0);

                isNew = true;
            }

            Disk wJob = waitingJob.poll();
            // 기존에 대기하던 작업과 다른 새 작업은 계산 방법이 다르다.
            if( isNew ) {
                sum += wJob.taskTime;
                prev_end = wJob.requestTime + wJob.taskTime;

            } else {
                sum += ((prev_end-wJob.requestTime) + wJob.taskTime);
                prev_end += wJob.taskTime;

            }
        }

        return (int) sum/len;
    }
}

문제를 정확히 이해하지 못한 상태에서 코드를 써내려갔다. 잘 못이해한 지점부터 다시 정신을 차리고 문제를 풀어야 하는데 한번 나간 멘탈은 돌아오지 않는다. 그래서 시간이 너무 많이 흘렀다. 문제를 풀 때, 방향을 빨리 정하지 못하거나 전혀 다른 방향으로 풀기 시작하면 많은 시간과 에너지가 허비된다. 그 대신 문제를 정확히 이해하고, 푸는 방법이 정확하면 그 문제는 어떻게든 시간 내에 풀린다.