디스크 컨트롤러(프로그래머스-힙)

문제

코드

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        List<int[]> list=new ArrayList<>();
        for(int[] arr:jobs)
            list.add(arr);
        Collections.sort(list,(a,b)->a[1]-b[1]);
        int time=0;
        while(!list.isEmpty()){
            boolean isSuccess=false;
            for(int i=0;i<list.size();i++){
                if(list.get(i)[0]<=time){
                    time+=list.get(i)[1];
                    answer+=time-list.get(i)[0];
                    list.remove(i);
                    isSuccess=true;
                    break;
                }
            }
            if(!isSuccess){
                int min=list.get(0)[0];
                int index=0;
                for(int i=1;i<list.size();i++){
                    if(min>list.get(i)[0]){
                        min=list.get(i)[0];
                        index=i;
                    }
                }
                time=list.get(index)[0]+list.get(index)[1];
                answer+=list.get(index)[1];
                list.remove(index);
            }
        }
        return answer/jobs.length;
    }
}

풀이

(1) 입력으로 들어온 작업들을 ArrayList형으로 만들어 준다. (완료된 작업은 제거해 주기 위해서)
(2) ArrayList를 소요시간이 짧은 순대로 오름차순 정렬해준다.
(3) 모든 작업이 완료될때 까지 반복문을 실행한다.

• 지금 실행할 수 있는 작업(작업 요청시간이 현재 시간보다 크지 않은 작업)중에 소요시간이 가장 작은 작업을 완료한다.
• 만약 지금 실행할 수 있는 작업이 없다면, 가장 먼저 실행할 수 있는 작업을 완료한다.
• 작업을 완료할 때마다 현재 시간에서 작업 요청시간을 뺀 것을 answer에 더해준다.

(4) 위 과정을 통해 모든 작업을 완료하면, answer을 작업 개수로 나눈 평균을 출력한다.

결과

카테고리는 힙 문제이지만, 나는 그냥 Collentios.sort를 통해 소요시간 짧은 것부터 정렬하여 풀었다. 힙을 쓰는것과 별 차이는 없을 것이라 생각한다.
처음에는 소요시간이 짧은 것부터 완료하고, 만약 지금 실행할 수 있는 작업이 없다면, 다음 소요시간 짧은 작업을 실행할 수 있을때까지 기다리는 방식으로 풀었는데, 통과하지 못했다.
그래서 다른 반례를 구해서 다시 풀었다.
지금 실행 할 수 있는 작업이 없다면, 소요시간이 다음으로 짧은 작업이 아니라 가장 먼저 실행할 수 있는 작업을 선택했어야 했다.
이 부분도 생각하고 구현하는데에는 어려움이 없었지만, 구현 중 실수로 자꾸 틀린 답이 나와서 고생좀 했다.
요즘따라 문제를 푸는데 마음이 급하다. 빨리 풀려고 하는 것 보다 실수를 하지 않는게 길게 보면 시간을 훨씬 아낀다는 생각으로 신중하게 풀어야겠다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges