[Algorithm] Programmers :: 선입 선출 스케줄링

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

프로그래머스

int solution(int n, vector<int> cores) 
{
    int left = 0;
    int right = 200000;
    int mid = 0;
 
    if (n <= cores.size())
    {
        return n;
    }
 
    while (left + 1 < right)
    {
        int mid = (left + right) / 2;
        int workCounts = cores.size();
 
        if (mid > 0)
        {
            for (int i = 0; i < cores.size(); ++i)
            {
                workCounts += mid / cores[i];
            }
        }
 
        if (workCounts < n)
        {
            left = mid;
        }
        else 
        {
            right = mid;
        }
    }
 
    int leftCounts = cores.size();
 
    for (int i = 0; i < cores.size(); ++i)
    {
        leftCounts += left / cores[i];
    }
 
    for (int i = 0; i < cores.size(); ++i)
    {
        if ( (left+1) % cores[i] == 0)
        {
            ++leftCounts;
        }
 
        if (leftCounts == n)
        {
            return i + 1;
        }
    }
}

 

일일이 하나씩 계산하면 시간초과.

그래서 우선순위큐로 매 시간씩 진행하면서 작업완료된것들을 체크하고 갱신시켜주는 식으로 했어도... 시간초과가 나왔다. 솔직히 이건 될 줄 알았는데;; 문제가 요구하는 능력이 다른것임을 깨달았다.

 

다른 사람의 풀이를 보니까 파라매트릭서치를 사용했다고 하길래, 처음 알게되는 키워드라 해당 기법부터 알아봤다.

문제를 재해석해서 구해야하는 해를 재설정한 다음에, 해당 해를 이분탐색으로 구하는 문제였다.

풀이를 안봤더라면 몇시간을 고민하든 못풀었을 것 같다.

 

봤던것 중 제일 이해 쉬운 풀이는 아랫글.

https://dev-note-97.tistory.com/173

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

 

이분탐색에 대한 글

 

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

 

이번 문제덕분에  새로운 영역을 조금 확장했다.