[PriorityQueue][Medium] 621. Task Scheduler.

https://leetcode.com/problems/task-scheduler/description/

 

char 열의 입력이 주어진다. 

각 문자는 task를 의미하고, 각 task를 한 후 n 만큼 해당 task를 idle 하고 해야 한다.

이때 모든 task를 처리하기 위한 cycle 수를 구하라.

 

 

실 사례에 알고리즘을 적용하기 좋은, 괜찮은 문제다. 

 

우선 등장하는 task가 알파벳 대문자로 주어졌다. 

같은 task대로 우선 빈도수로 정리를 해 본다. 

빈도수와 task처리는 어떤 관계가 있을지 먼저 생각해 본다.

idle 시간을 고려하여 많은 빈도수의 task를 먼저 처리해야 최종 cycle이 줄어 든다. 

 

최종 그림은 아래와 같이 설계할 수 있게 된다. 

 

"빈도수가 많은 할 수 있는 상태의 Task를 먼저 처리한다."

 

이것이 기본 규칙이 된다. 

 

우선 task를 빈도 수 대로 정리한다.

많은 수대로 task를 처리 할 것이므로, 정렬하거나 priority queue를 쓴다. 

다음으로 한번 task를 처리하면 어떻게 되나? 

 -> 빈도수를 1 줄이고 다시 정렬하거나 priority queue에 넣어 큰 순서대로 처리케 한다. 

 -> 다만 이때 빈도수가 0이되면 그냥 제거 한다.

 -> 이때 n 만큼의 idle 시간이 필요하니 이것을 고려한다. 

 -> 더 이상 처리할 task가 없게되면 종료.

 

코드

int leastInterval(vector<char>& tasks, int n) 
{
    unordered_map<char, int> mFreq;
    for (int q = 0; q < tasks.size(); ++q)
        mFreq[tasks[q]]++;

    priority_queue<int> maxPQ;
    for (auto iter = mFreq.begin(); iter != mFreq.end(); ++iter)
        maxPQ.push(iter->second);

    int turn = 0;
    queue<pair<int, int>> qJob;	// turn, freq
    while (qJob.size() > 0 || maxPQ.size() > 0)
    {
        if (qJob.size()>0 && qJob.front().first <= turn)
        {
            maxPQ.push( qJob.front().second );
            qJob.pop();
        }

        if (maxPQ.size() > 0)
        {
            int freq = maxPQ.top();
            maxPQ.pop();

            if (freq - 1 > 0)
                qJob.push(make_pair(turn + n + 1, freq - 1));
        }
        ++turn;
    }
    return turn;
}

 

 

 

결과