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

문제설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한사항

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

전체코드(Java)

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int start_time = 0;
        int total_time = 0;
        int wating_time = 0;
		int current_time = 0;
        List<int[]> endProcess = new ArrayList<>();
		// 작업의 시간이 짧은것부터 정렬하여, 대기시간을 최소화 할 수 있도록 우선순위 큐를 정렬한다.
		PriorityQueue<int[]> jobList = new PriorityQueue<>(jobs.length,
				(int[] o1,int[] o2)-> o1[1]==o2[1]?o1[0]>o2[0]?1:-1:o1[1]>o2[1]?1:-1
				);
        
        Arrays.sort(jobs,(int[] a1,int[] a2) -> a1[0]==a2[0]?a1[1]>a2[1]?1:-1:a1[0]>a2[0]?1:-1);
        
		// 첫번째 프로세스부터 jobList에 넣는다.
        jobList.add(jobs[0]);
        // 첫번째 작업이 들어온 시간을 저장한다.
        current_time = jobs[0][0];
        
		// 실제 작업시간은 대기시간과는 별개이므로 실제 작업시간만 total에 누적으로 저장하고, answer에는 대기시간+작업시간을 누적으로 저장한다.
		while(!jobList.isEmpty()) {
			
            // 처리해야할 process를 처리 후 endProcess에 넣고, 작업시간(total_time)과 대기시간(working_time)을 포함한 시간을 업데이트한다.
            int[] task = jobList.poll();
            endProcess.add(task);
            
            wating_time = current_time>task[0]?current_time-task[0]:0;
            
            // 각 프로세스의 작업시간을 current_time에 누적한다.
            current_time  +=  task[1];
            // 대기시간과 작업시간의 합을 totla_time에 누적한다.
            total_time += wating_time + task[1];
            
            // 들어온 작업들의 순서를 다시 재배치
			jobList = rearrangeList(jobList,endProcess,jobs,current_time);
		}
		// 작업의 평균 시간을 구해야하므로, total_time를 작업의 개수로 나눈다.
        System.out.println();
        return total_time/jobs.length;
    }
    
    public static PriorityQueue<int[]> rearrangeList(PriorityQueue<int[]> jobList,List<int[]> endProcess,int[][] jobs,int total_time){
		
        List<int[]> remainProcess = new ArrayList<int[]>();
        
        // 기존에 존재하는 작업리스트를 모두 제거한다.
        jobList.clear();
        
        // jobs 2중 배열의 작업 중 현재 작업한 시간보다 일찍 들어왔고, 끝난 작업이 아닌 작업들만 다시 jobList에 넣는다.
		for(int[] j : jobs) {
            if(j[0]<=total_time && !endProcess.contains(j))
                jobList.add(j);
            else if(j[0]>total_time && !endProcess.contains(j)){
                remainProcess.add(j);
            }
		}
		
        // 현재시간보다 대기하고 있는 작업이 있다면 미리 땡겨서 실행한다.
        if(jobList.isEmpty() && remainProcess.size()>=1){
            Collections.sort(remainProcess,(int[] o1,int[] o2)-> o1[1]==o2[1]?o1[0]>o2[0]?1:-1:o1[1]>o2[1]?1:-1);
            jobList.add(remainProcess.get(0));
        }
        
		return jobList;
	}   
}

 

혹시라도 정정할 내용이나 추가적으로 필요하신 정보가 있다면 댓글 남겨주시면 감사하겠습니다.

오늘도 Jindory 블로그에 방문해주셔서 감사합니다.

 

[ 참고 ]

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