Today's Algorithm(2018-12-17)

programmers. 디스크 컨트롤러

자료구조를 만들고 그것을 이용하여 제가 원하는 데이터를 찾는 과정이 쉽지 않았습니다. 왜냐하면 첫째로 제가 만든 자료구조가 복잡했고, 그 사이에서 또 정렬이 필요하였기 때문입니다. 우선 제가 만든 자료구조는 2개였습니다.

1. Map<Integer, Queue<Job>> : 각 시간에 해당하는 작업들을 모아두었습니다.
2. Queue<Job> : 현재 대기중인 작업들을 모아두었습니다.

 

그럼 이러한 자료구조를 기반으로 풀이과정을 설명해볼게요.

• 먼저 jobs 가 주어지면 init() 메서드에서 위의 map 자료구조를 만듭니다.
• 경과 시간을 재는 elapsedTime 과 각 작업의 남은 시간을 재는 remainingTime 라는 변수를 만들고 반복문을 돌립니다.
• 반복문은 map과 queue가 모두 비워질 때 그만두고 그 외엔 계속 반복문이 가동됩니다. 그리고 반복문 안에서 map 내에 해당 경과시간의 value가 있으면 queue에 추가하고 map 내 value는 없앱니다. 또 queue에 작업이 남아있고 남은 작업 시간이 0일 때 Queue에서 가장 작업시간이 작은 작업을 꺼내 remainingTime 을 갱신합니다.
• 이전 반복문에서 Queue에서 작업을 꺼낼 때 answer += (elapsedTime + job.operationTime - job.startTime) 을 통해 해당 작업이 요청으로부터 종료까지 걸린 시간을 더해줬었는데요. 문제에서 요구되는 값은 평균값이기 때문에 총 작업 크기만큼 나누기를 합니다.

 

코드로 나타내면 다음과 같습니다.

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;

        Queue<Job> queue = new PriorityQueue<>();
        Map<Integer, Queue<Job>> map = new HashMap<>();
        init(jobs, map);

        int elapsedTime = 0;
        int remainingTime = 0;
        while(!map.isEmpty() || !queue.isEmpty()) {
            if(map.containsKey(elapsedTime)) {
                queue.addAll(map.get(elapsedTime));
                map.remove(elapsedTime);
            }

            if(!queue.isEmpty() && remainingTime == 0) {
                Job job = queue.poll();
                remainingTime = job.operationTime;
                answer += (elapsedTime + job.operationTime - job.startTime);
            }
            elapsedTime++;
            if(remainingTime > 0) remainingTime--;
        }

        return answer / jobs.length;
    }

    private void init(int[][] jobs, Map<Integer, Queue<Job>> map) {
        for (int i = 0; i < jobs.length; i++) {
            int startTime = jobs[i][0];
            int operationTime = jobs[i][1];
            Job job = new Job(startTime, operationTime);

            if (!map.containsKey(startTime)) {
                Queue<Job> part = new PriorityQueue<>();
                part.offer(job);
                map.put(startTime, part);
            } else {
                map.get(startTime).add(job);
            }
        }
    }


    class Job implements Comparable<Job> {
        int startTime;
        int operationTime;

        public Job(int startTime, int operationTime) {
            this.startTime = startTime;
            this.operationTime = operationTime;
        }

        @Override
        public int compareTo(Job o) {
            return this.operationTime - o.operationTime;
        }
    }
}

 

이번 문제에서 가장 핵심이 되는 것은 결국 'PriorityQueue 를 어떻게 잘 사용하느냐' 였습니다. 이번 프로그래머스 문제들을 풀면서 그 유용성에 대해선 확실히 배운 것 같네요!