[프로그래머스 Lv.4] 선입 선출 스케줄링 - JAVA

문제 링크 : programmers.co.kr/learn/courses/30/lessons/12920

코딩테스트 연습 - 선입 선출 스케줄링

 

접근 과정 

   1) 우선순위 큐와 반복문을 활용한 풀이

• 우선순위 큐를 이용하여 core들을 순회시켰다. 
• 반복문안에서 core들이 순서대로 작업을 1개씩 담당하며 처리했고 n은 차감되었다.
• n이 0이 되었을 때, 마지막 작업을 처리한 core의 인덱스를 출력하였다.

      => 정확성은 통과하였으나, 효율성에서 시간초과라는 결과를 보였다. 

 

   

   2) 시간이 Time일 때, 처리한 작업을 구하는 Count함수와 구할 시간을 찾는 이분탐색을 활용

•  시간이 time일 때, 그 시간까지 처리한 작업의 수량을 리턴하는 CountWork 함수를 구현하였다.
•  초기 min = 0, max = (core[0]*n)으로 두고 이분탐색을 진행하였다.
•  처음으로 n이상의 작업을 처리한 시간 time을 탐색하였다.
•  time까지 처리한 작업량과 n의 차이와 time에 작업을 처리한 core의 index를 비교하여 n을 처리하는 core의 인덱스를 출력하였다.

      => 정확성과 효율성 모두 통과

 

소스 코드 및 결과

  Code 1 : 우선순위 큐와 반복문을 활용

 public static int solution(int n, int[] cores) {
        int answer = 0;

        if (n <= cores.length) { // n이 core의 개수보다 작을 경우 n번째 코어를 리턴
            return n;
        }

        n -= cores.length;  // 시간이 0일 때, 모든 코어가 작업을 하나씩 담당하여 처리

		// 다음 처리시간순으로 정렬, 처리시간이 같을 경우는 index값이 작은 순으로 정렬
        PriorityQueue<core> pq = new PriorityQueue<>((q1, q2) -> {  
            if (q1.time == q2.time) {
                return q1.index - q2.index;
            }
            return q1.time - q2.time;
        });

        for (int i = 0; i < cores.length; i++) { // core를 pq에 삽입
            pq.add(new core(i, cores[i]));
        }

        int time = 1;
        while (n > 0) { // n이 0이 될 때까지 core가 작업을 하나씩 담당 처리

            core now = pq.poll(); // 다음 작업을 처리할 core

            if (now.time == time) {  // 현재시간과 core의 다음처리시간이 같은 경우
                n--;
            } else if (now.time > time) { // 현재시간보다 core의 다음처리가 큰 경우
                time = now.time;
                n--;
            }

            if (n == 0) { // 작업이 모두 처리되었으니, core의 인덱스를 출력
                answer = now.index + 1;
            } else {
            	// 작업이 남은경우, 사용한 core의 다음 처리시간을 구하여 pq에 삽입
                pq.add(new core(now.index, time + cores[now.index])); 
            }
        }

        return answer;
    }
}

class core {
    int index;
    int time;

    public core(int index, int time) {
        this.index = index;
        this.time = time;
    }
}

결과 : 

 

 

  Code 2 : 이분탐색을 활용

 public static int solution(int n, int[] cores) {
        int answer = 0;

        int min = 0; // 시간의 최소값
        int max = cores[0]*n; // 시간의 최대값

        int time = 0;
        int m = 0; // time까지 처리한 작업량

        while (min <= max) {  
            int mid = (min+max)/2;

            int count = CountWork(mid, cores);

            if (count >= n) { // 해당시간까지 처리한 작업량보다 n이 크면 time과 m갱신
                max = mid-1;   
                time = mid;     
                m = count; 
            }else{
                min = mid+1;
            }
        }

        m-=n; // 처리한 작업량과 n의 차이 갱신
        for(int i = cores.length-1; i>=0; i--){
            if (time % cores[i] == 0) { // 시간이 time일때, 작업을 처리하는 core
                if (m == 0) {
                    answer = i+1;
                    break;
                }
                m--;
            }
        }

        return answer;
    }

    static int CountWork(int time, int[] cores){

        if (time == 0) { // 시간이 0일 때, 처리할 수 있는 작업량은 코어의 개수 
            return cores.length;
        }

        int count = cores.length; // 시간이 0일 때, 처리한 작업량 

        for(int i = 0; i<cores.length; i++){ // time까지 코어가 처리할 수 있는 작업량 합산
            count += (time/cores[i]);
        }

        return count;
    }
}

결과 :