(코테) 프로그래머스_선입 선출 스케줄링 *이진탐색

 

 

 

문제링크

 

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

 

 

 

 

class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        
        //핵심 시간 찾기
        long min_time = 0;
        long max_time = 50000 * 10000;
        long avg_time = 0;
        
        while(min_time<=max_time){
            long mid = (min_time+max_time) / 2 ;
            long cnt = cores.length;
            for(long next:cores)  cnt += mid/next;           
            
            //min,max 최적 조합해주기
            if(cnt >= n ){
                avg_time = mid;
                max_time = mid-1;                                
            }else{
                min_time = mid+1;
            }
            
        }
        int prev_cnt = cores.length;
        //핵심시간 -1        
        for(int core : cores){
           prev_cnt +=  (avg_time-1)/core ;
        }         
        
        //인덱스 찾기      
        for(int i=0; i<cores.length ;i++){
            if(avg_time%cores[i]==0){
             prev_cnt++;
                if(prev_cnt==n){
                    answer = i + 1;                
                    break;
                }
            }        
            
        }
        
        
        return answer;
    }
}

 

 

회고

 

1. 우선순위큐 처음 떠올린 생각은 큐에 넣고 시간에 맞게 꺼내고 넣고를 생각햇다. 

근데 모든 순회를 돌고 offer , poll 등으로 내부적 시간복잡도가 높아져서 시간초과하게 되는 코드가 된다.

 

2. 해결 알고리즘   이진탐색

우선 max값들이  core = 10000    n = 50000 이하로 

최대 시간은 10000*50000이다 이걸로 이진탐색으로 쪼개며 최적의 시간을 구한 후 그 시간에서 1초를 뺸 후 for문 순회 한번으로  어떤 인덱스에서 작업하는지 찾는 방식으로 접근