[프로그래머스 Level.3] 선입 선출 스케줄 (연습문제) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 선입 선출 스케줄

 

 

 

문제 설명

 

 

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

 

• CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

 

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

 

 

 

제한 사항

• 코어의 수는 10,000 이하 2이상 입니다.
• 코어당 작업을 처리하는 시간은 10,000이하 입니다.
• 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

 

---

 

입출력 예

n	cores	result
6	[1,2,3]	2

 

 

 

입출력 예 설명

 

 

입출력 예 #1

 

처음 3개의 작업은 각각 1,2,3번에 들어가고, 1시간 뒤 1번 코어에 4번째 작업,다시 1시간 뒤 1,2번 코어에 5,6번째 작업이 들어가므로 2를 반환해주면 됩니다.

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        
        // target => 총 작업 시간
        int start = 1;
        int end = cores[0] * n; // 코어 한개가 n개의 일을 다하는 경우(최대)
        int time = 0; // n개 이상의 작업이 처음으로 들어가는 시간
        int count = 0;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            int sum = cores.length; // 처음에 코어에 작업이 각각 한 개씩 들어감
            
            // 해당 시간(mid)까지 코어(core)가 완료한 일의 개수 합산
            for(int core : cores) sum += mid / core; 
            
            if(sum >= n) {
                end = mid - 1;
                time = mid;
                count = sum;
            } else {
                start = mid + 1;
            }
        }
        
        count -= n; // 해당 시간(time)까지 들어간 작업과 n의 차이
        for(int i=cores.length-1; i>=0; i--){
            if(time % cores[i] == 0) { // 시간이 time일때, 작업을 끝내고 새로 시작한 core
                if(count == 0) {
                    answer = i + 1;
                    break;
                }
                
               count--;
            }
        }
        
        return answer;
    }
}

 

풀이

1. 이분 탐색(Binary Search)을 이용하여 n개 이상의 작업이 처음 시작되는 시간(time)을 구하고 해당 시간에 작업을 끝내고 새로 작업을 시작한 코어(core)들 중에 n번 째 작업을 시작한 코어(core)를 구한다.
2. 우선 target을 n개 이상의 작업이 처음 시작되는 시간(time)으로 잡고 최선의 경우(start)를 1, 최악의 경우(end)를 한 개의 코어가 작업 n개를 모두 하는 경우인 core[0] * n으로 한다.
3. n개 이상의 작업이 시작되는 시간을 구했을 때 해당 시간에 작업의 개수를 담을 count를 0으로 초기화한다.
4. 이제 start가 end보다 커지면 종료하는 while문을 생성하고 start와 end를 더하고 2로 나눠 mid에 저장한다.
5. 해당 mid의 시간 동안 작업한 진행하는 작업의 수를 저장할 int형 변수 sum을 core.length로 초기화 한다. (처음에 각 코어에 작업이 들어가므로 코어의 개수로 초기화)
6. 그리고 각 코어가 cores를 순회하면서 mid / cores[i]를 이용해 해당 time까지 완료한 작업의 양을 sum에 더해준다.
7. 그러면 sum에는 해당 시간(time)에 작업에 들어간 양이 담기게 된다.(time이 2초라면 2초까지 완료한 작업 + 작업 중인 작업)
8. 이제 sum과 n을 비교하여 sum이 n 이상이라면 time을 mid로 저장하고 count에 sun을 저장한 후에 end를 mid - 1로 변경하여 n 이상의 작업을 시작하는 더 최선의 시간(time)을 찾고 sum이 n보다 작다면 start를 mid + 1로 변경하여 가능한 시간(time)을 다시 탐색한다.
9. 이분 탐색을 마치고 해당 시간(time)을 찾았다면 이제 해당 시간에 들어간 n 이상의 작업인 count에서 n을 뺀다. (count에서 n을 빼면 해당 시간까지 들어간 작업량과 n의 차를 구할 수 있다)
10. 해당 시간에 작업을 들어감으로써 처음으로 n 이상이 된 것이므로 이 둘의 차는 해당 시간 time에 새로 시작한 작업의 수와 같다.
11. 동시에 작업이 끝난다면 앞의 코어부터 작업을 시작하므로 cores를 뒤에서부터 순회하면서 (time % cores[i] == 0)을 이용하여 해당 시간에 작업이 끝나 작업을 새로 시작하는 코어(작업이 끝나면 곧바로 새로 작업 시작)를 찾는다.
12. 만약 count가 0이라면 해당 코어의 번호인 인덱스 + 1을 answer에 저장하고 반환하고 아니라면 count를 - 1 하고 앞의 코어를 탐색하여 n번 째 작업을 시작하는 코어의 번호를 구해 answer에 저장하고 반환하면 된다. 

 

참고 : https://rays-space.tistory.com/15