[프로그래머스][level4] 선입 선출 스케줄링 (C++)

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

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

 

 

[난이도] level4
[유형] 이분탐색

[풀이]
어떤 코어에서 일의 처리가 완료될때마다 그 코어에 새로운 작업을 할당해주고,
나머지 코어의 일의 남은 시간을 업데이트 하는 방식을 생각할 수 있는데 이런 방식으로는
코어의 개수 N이 10000, 처리해야할 일의 개수가 50000개 이므로 O(N*M)이 되어 시간내에
해결할 수가 없습니다.

이런 유형의 문제에는 이분탐색(파라메트릭 서치)를 이용해야 합니다.

최저시간 low=-1, 최고시간 high=200000로 두고
어떤 시간 mid가 지났을 때, 처리한 총 일의 개수 cnt를 기준으로 low 혹은 high를 mid로 업데이트해줍니다.

(코어의 수가 2개, 각각의 처리시간은 10000, 총 일의 개수가 50000일때가 시간이 가장 오래 걸리는 케이스입니다.
이때 모든 일을 처리하는데 (10000*50000)/2 시간이 걸리는데 high을 200000 정도로만 잡아도 통과를 합니다.
TC가 부족한 것 같습니다.)

처리한 총 일의 개수는 (mid(시간)/cores[i])+1 들의 합으로 구할 수 있습니다.
예를 들어 일 한개를 처리하는데 2시간이 걸리는 코어의 일처리 과정을 시간별로 보면
아래와 같이 (현재 시간을 코어의 처리시간으로 나눴을 때의 몫)+1 으로 표현됩니다.

0시간 : 1개
1시간 : 1개
2시간 : 2개
3시간 : 2게
4시간 : 3개
5시간 : 3게
6시간 : 4개
7시간 : 4개
....

이 때 목표 처리 물건 개수 n보다 적게 만드는 시간 중에 최고 시간이 lo로 수렴하도록 해야합니다.
이렇게 하면 lo+1 시간에 어떤 코어 i에 물건을 할당하면 최종적으로 n개를 처리할 수 있기 때문입니다.
0번 코어부터 N-1번 코어부터 확인하면서 lo+1 시간에 물건을 할당할 수 있는지를 검사해서 할당할 수 있으면
lo시간까지 처리한 물건의 개수에 1개씩 더해줍니다.
(lo+1)%cores[i]==0 을 만족하면 lo+1시간에 물건 할당이 가능하다는 것을 위의 일처리 과정 예시를 보면 확인할 수 있습니다.

lo가 -1로 나온 경우는 처리해야할 일의 개수가 코어 개수보다 적은 것이므로 n번째 일을 처리하는 n번 코어를 리턴해주기만 하면 됩니다.

이런 유형의 문제를 이분탐색으로 처리할 생각을 하기가 쉽지는 않지만 꽤 자주 보이는 전형적인 유형이므로
익혀두면 도움이 될 것 같습니다.

 

 

#include <vector>
#include <cstdio>
using namespace std;
int solution(int n, vector<int> cores) {
    int lo=-1,hi=2e5,mid=0;
    while(lo+1<hi){
        mid = (lo+hi)/2;
        int cnt=cores.size();
        if(mid>0) for(int i=0;i<cores.size();i++) cnt+=mid/cores[i];
        if(cnt<n) lo=mid;
        else hi=mid;
    }
    if(lo==-1) return n;
    int cnt=cores.size();
    for(int i=0;i<cores.size();i++) cnt+=lo/cores[i];
    for(int i=0;i<cores.size();i++){
        if((lo+1)%cores[i]==0) cnt++;
        if(cnt==n) return i+1;
    }
    return 0;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/선입_선출_스케줄링.cpp