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

(문제 설명)

(제한 사항)

 

해당 문제는 CPU 스케줄링 알고리즘 중 SJF(Shortest Job First) 알고리즘 구현 문제이다.

가장 짧게 수행하는 프로세스가 우선순위가 높게 선정되어 CPU를 점유하게 되면 전체 처리 평균 시간을 줄일 수 있다.

(하지만 이 알고리즘의 단점은 수행 시간이 긴 프로세스들을 계속해서 CPU를 점유할 수 없다는 것.)

 

 

알고리즘 구현 방법

 1. 배열 jobs[][] 정렬

 2. 요청이 들어온 작업 Map에 넣기

 3. 소요시간이 가장 적은 작업부터 Map에서 제거하기

     (2,3번 반복)

 4. 요청시간 평균 구하기

 

    public static void main(String[] args) {
        /*14*/ int[][] jobs = {{0, 10}, {2, 10}, {9, 10}, {15, 2}};
        
        // jobs 배열 정렬
        Arrays.sort(jobs, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0])
                    return o1[1] - o2[1];
                else
                    return o1[0] - o2[0];
            }
        });
		
        int result = 0;

        TreeMap<Integer, ArrayList> map = new TreeMap<>();        // TreeMap<소요시간, 시작시간> 사용
        map.put(jobs[0][1], new ArrayList<>(jobs[0][0]));
		
        int time = jobs[0][0];
        int i = 0, count = 0;
        while(true) {
            if(count == jobs.length) break;                        // 수행된 작업이 모두 카운트되면 빠져나감

// 수행되고 있는 시간동안 대기할 수 있는 작업들 Map에 넣기
            if(i<jobs.length && jobs[i][0] <= time) {
                if(i < jobs.length) {
                    if(map.containsKey(jobs[i][1])) {                // 동일한 수행시간이 존재할 경우, value 값에 추가하기
                        ArrayList<Integer> tmp = new ArrayList<>(map.get(jobs[i][1]));
                        tmp.add(jobs[i][0]);
                        map.replace(jobs[i][1], tmp);
                    }
                    else { 
                        ArrayList<Integer> tmp = new ArrayList<>();
                        tmp.add(jobs[i][0]);
                        map.put(jobs[i][1], tmp);
                    }
                    i++;
                }
            }
// 더이상 작업이 존재하지 않거나, 다른 작업이 수행될 시간 동안 대기하는 작업이 없을 경우.
            else {
                if(!map.isEmpty()) {
                    int key = map.keySet().iterator().next();
                    time += key;
                    result += (time-((int)map.get(key).get(0)));
					
                    if(map.get(key).size() > 1) map.get(key).remove(0);                // value가 여러개 일 경우, 제일 첫번째꺼만 지움.
                    else map.remove(key);                // value가 하나일 경우, 키 자체를 지움.
                    count++;                             // 수행된 작업 카운트
                }
                else {                // 테스트케이스 6번째와 같은 경우, 수행시간은 다시 count됨.
                    time = jobs[i][0];
                }
            }
        }
        result = result/jobs.length;
        System.out.println(result);
    }