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

문제

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

풀이

이 문제는 주어진 작업들을 순서대로 처리할 때 마지막 작업을 담당하는 코어 번호를 구하는 문제이다. 핵심은 주어진 작업 개수를 처리할 수 있는 최소 시간을 먼저 찾아내는 것이라고 생각했다.

항상 이런 식으로 요구 조건을 만족시키는 시간을 구하는 문제를 해결할 때, 시간을 0부터 1씩 증가시키며 구하면 시간 초과가 발생한다. 이분 탐색을 통해 시간을 구해야 요구 되는 시간 복잡도를 만족 시킬 수 있다. (1씩 증가시키는 방법으로 제출해보지 않아서 실제로 시간 초과인지는 모름)

조건을 만족 시키는 시간(end)을 구한 후, 배열의 뒤에서부터 나누어 떨어지는 곳을 찾았을 때, 해당 위치가 마지막으로 작업이 할당되는 core라고 생각했다. 하지만, 해당 시간(end)에 할당되는 작업의 총 개수가 남은 작업의 개수보다 많을 수 있다는 것을 알게 되었고, 이전 시간(end - 1)까지 할당된 작업의 총 개수를 구하고 남은 작업의 개수만큼 앞에서부터 할당하는 방식으로 수정하여 문제를 해결했다.

소스 코드

C++17

#include <bits/stdc++.h>

int solution(int n, std::vector<int> cores) {
    if (n <= cores.size()) {
        return n;
    }

    int start = 0, end = INT_MAX;

    const auto executable = [&] (int time) {
        return std::accumulate(
            cores.begin(), cores.end(), 0LL,
            [time] (long long acc, int core) { return acc + time / core + 1; }
        );
    };

    while (start < end) {
        const int mid = (start + end) / 2;

        if (executable(mid) < n) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }

    const long long done = executable(end - 1);
    long long left = n - done;

    for (size_t i = 0; i < cores.size(); i++) {
        if (end % cores[i] == 0) {
            if (--left == 0) {
                return i + 1;
            }
        }
    }

    return -1;
}

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

문제

풀이

소스 코드

Share this post