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;
}
결과
'Leetcode > NeetCode' 카테고리의 다른 글
[BackTrack][Medium] 39. Combination Sum (1) | 2024.07.23 |
---|---|
[👍][BackTrack][Medium] 78. Subsets (1) | 2024.07.23 |
[PriorityQueue][Medium] 215. Kth Largest Element in an Array (1) | 2024.07.20 |
[PriorityQueue][Medium] 973. K Closest Points to Origin (0) | 2024.07.20 |
[PriorityQueue][Easy] 1046. Last Stone Weight (0) | 2024.07.20 |