[프로그래머스] Lv3 선입 선출

 

문제 풀이 방법 

문제에선 마지막 작업을 처리하는 코어의 번호를 return하라고 합니다.

마지막 작업을 처리하는 코어번호를 알기 위해선 이 작업들을 전부 완료했을때, 언제 끝나는지 알아야 합니다.

즉, 이 작업들을 끝낼 수 있는 최소 시간을 먼저 찾아야 합니다.

 

처음엔 우선순위큐를 사용해서 문제를 풀었지만 효율성 처리 부분에서 시간초과가 떴습니다.

"작업들을 끝낼 수 있는 최소 시간"을 찾아야 하기 때문에 효율적으로 탐색할 수 있는 방법인 이분 탐색을 통해 최소 시간을 찾아줍니다.

 

잠깐! 이분 탐색을 사용하려면 정렬을 하고 탐색을 해야하지 않나요?

 

이분 탐색을 하기 전에 정렬을 하고 찾는 것은 맞는 말이지만, 이 문제에서 찾고자 하는 값은 최소 시간입니다.

최소 시간을 찾는 시간의 범위 자체는 이미 정렬이 되어 있기 때문에 정렬을 따로 해줄 필요는 없습니다.

 

이분 탐색으로 주어진 작업을 모두 실행시킬 수 있는 최소시간을 도출하고, 하나의 작업 처리를 해줘야 합니다.

이 문제에서 궁극적으로 물어보는 것은 마지막 작업을 처리하는 코어번호를 알아내는 것입니다.

 

마지막 작업을 처리하는 코어번호는 어떻게 선별할 수 있을까요?

 

마지막 작업 이전까지 완료된 작업 수를 먼저 구한 후, 마지막 작업이 진행될 때 수행되는 작업 개수를 계산합니다.
마지막 이전 작업까지는 이미 모든 코어가 작업을 완료한 상태이므로, 모든 코어가 현재 작업을 수행할 준비가 되어 있습니다.
이제 모든 코어를 순차적으로 확인하는 것이 아니라, 최소 시간에서 실행될 수 있는 코어들만 선별하여 남아 있는 작업을 하나씩 할당합니다. 이렇게 할당을 진행하다가, 남아 있는 작업이 0이 되는 순간, 해당 코어가 마지막 작업을 실행한 코어가 됩니다.

 

 

풀이 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        
        int coresLength = cores.length;
        
        int start = 1;
        int end = 10000 * coresLength;
        int minTime = end;
        
        if(n <= coresLength) {
            return n;
        }
        
        while(start <= end) {
            int mid = (start + end) / 2;
            int finishTask = proceededTask(mid, cores);
            
            if(finishTask >= n) {
                minTime = mid;
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }
        
        int beforeTask = proceededTask(minTime - 1, cores);
        int remainTask = n - beforeTask;
        
        for(int i = 0; i < coresLength; i++) {
            if(minTime % cores[i] == 0) {
                remainTask--;
                if(remainTask == 0) {
                    return i + 1;
                }
            }
        }

        
        return -1;
    }
    
    private int proceededTask(int time, int[] cores) {
        int cnt = cores.length;
        
        for(int i = 0; i < cores.length; i++) {
            cnt += time / cores[i];
        }
        
        return cnt;
    }
}

 

시간 복잡도

while(start <= end) {
            int mid = (start + end) / 2;
            int finishTask = proceededTask(mid, cores);
            
            if(finishTask >= n) {
                minTime = mid;
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }

 

O(N) = 코어의 길이 * logN

 

for(int i = 0; i < coresLength; i++) {
            if(minTime % cores[i] == 0) {
                remainTask--;
                if(remainTask == 0) {
                    return i + 1;
                }
            }
        }

 

O(N) = 코어의 길이

 

최종적으로 log N * 코어의 길이가 됩니다.

 

출력 결과