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

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 core가 처리해야하는 작업이 있다면, 모든 작업을 처리할 경우 몇 번째 코어가 최종작업을 실행하는지를 찾는 문제다.

 

특정 시간에 각 core가 처리한 작업의 수를 찾는 방법은 나눗셈을 이용하면 쉽게 계산할 수 있다.

그렇기 때문에 n개의 작업을 처리할 수 있는 특정 시간을 찾으면 몇 번째 코어가 최종 작업을 실행하는지 알 수 있다.

 

여기서 특정 시간을 찾는 방법은 이분탐색으로 쉽게 찾을 수 있다.

이분탐색을 사용할 경우 log(N)의 시간 복잡도로 탐색을 할 수 있기 때문에 이 문제의 시간 복잡도는 코어의 수*log(N) 이 된다.

 

여기서 주의할 점은 특정 시간에 수행할 수 있는 작업은 0시간에는 core의 수 만큼 작업을 할 수 있다.

그러므로 m시간 후에 할 수 있는 작업은 ([m시간/core의 작업시간]의 몫 +1) 으로 나타내야 한다.

 

여기서 m시간을 core의 작업시간으로 나눴을 때, 나머지가 0인 경우는 막 작업을 시작했다는 뜻이다.

 

이 점에 유의하면, n개의 작업을 완료할 수 있는 최소 시간을 구할 수 있다.

(m시간에 할 수 있는 작업을 w라고 하면,   n<=w일 경우 ed=m-1,  n>w일 경우 st=m+1로 이분탐색을 한다) 

 

이제 최소 시간 m을 구했다면, 어떤 코어가 마지막으로 작업을 하는지 구하면 된다.

어떤 코어가 마지막 작업을 하는지 계산하는 방법은 여러가지가 있다.

 

그 중에서 나는 역으로 탐색하는 방법을 사용했다. 

 

최소시간이 m이라면 m-1시간에는 n개의 작업을 할 수 없다는 뜻이다.

 

이 점에 유의하면 m시간을 코어의 작업으로 나누었을 때 나머지가 0이 되는 코어들이 m시간에 새로 작업을 시작한다는 뜻이다.

그러므로 나머지가 0이 되는 코어들이 마지막 작업을 할 수 있는 후보들이 된다.

 

이제 마지막 작업을 하는 코어들의 후보를 찾았으면, 단순히 탐색을 하면된다.

m시간에 w개의 작업을 한다고 가정하자.

 

그러면 (n<=w)이므로 코어의 오른쪽 끝에서부터 나머지가 0이 되는 코어들을 찾는다.

만약 나머지가 0이 되는 코어가 나오면 현재 w가 n이랑 같은지 비교하고, 같으면 현재 코어를 return하면 된다.

만약 w가 여전히 n보다 크다면, w에서 작업의 수 1을 빼고 계속 탐색하면 된다.

 

만약 위 그림처럼 n이 31인데 최소 시간 m에 할 수 있는 작업 w가 33이나왔다고 가정해보자

 

f는 나머지가 0이지만, w가 33이므로 f 코어가 작업을 시작하면 w가 33이 된다는 뜻이다.

e는 나머지가 0이 아니므로, 고려할 필요가 없다.

d는 나머지가 0이지만, w가 32이므로 d 코어가 작업을 시작하면 w가 32가 된다.

c는 나머지가 0이고, w가 31이므로 c 코어가 31번째 작업을 시작한다는 뜻이다.

그러므로 마지막 작업인 31번째 작업은 c코어가 한다.

 

+ 앞에서부터 탐색을 해도 상관 없다.​

 

 

[아이디어 정리]

1. 나눗셈을 이용하면 특정 시간에 작업을 몇 개 하는지 계산할 수 있으므로, n개 이상의 작업을 하는 최소시간을 찾는다.
2. n개 이상의 작업을 하는 최소 시간은 이분탐색을 이용한다.
3. 최소 시간을 찾았다면 최소 시간 m때 작업을 시작하는 코어를 찾고, 그 때 몇 번째 코어가 n번째 작업을 시작하는지 찾아 return 한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int n, vector<int> cores) {
    int answer = 0;
    int st=0,ed=cores[0]*((n/cores.size())+1),mid; 
    int Work=0,fW=0; //fw -> 최소시간에 몇개의 작업을 할 수 있는지 저장할 변수
    while(st<=ed) //이분탐색
    {
        mid=(st+ed)/2;
        Work=0;
        for (int i=0; i<cores.size(); i++)
        {
            Work+=(mid/cores[i])+1; //작업의 수 계산
        }
        if (Work>=n)
        {
            ed=mid-1;
            fW=Work;
        }
        else
        {
            st=mid+1;
        }
    }
    for (int i=cores.size()-1; i>=0; i--)
    {
        if (st%cores[i]==0)
        {
            if (fW==n) //fw번째 작업을 하는 코어가 n번째 작업인지 판단
            {
                return i+1;
            }
            fW-=1;
        }
    }
    return answer;
}

 

---

문제의 아이디어는 빠르게 생각했는데, 풀이를 빠르게 하기 위한 잡생각을 좀 많이 했다...

다른 사람의 풀이도 비슷해서 실행해봤는데 시간이 2배정도 차이가 났다;;

아무리 고민을 해봐도 시간 초과가 날 이유가 전혀 없는데 거의 2배 가까이 일정하게 차이가 나길래 궁금해서 코드를 수정하면서 찾아봤다.

알고보니 이분 탐색을 할 때 변수를 그냥 long long으로 선언해서 사용해서 시간이 차이가 났다.

 

int는 4byte고 long long은 8byte니까 약 2배의 속도가 차이가 난 이유는 메모리에 할당하는 과정에서 일어난 것 같다;;

long long을 int로 바꾸니 바로 해결ㄷㄷㄷ

 

프로그래머스