[leetcode 621] Task Scheduler

- 문제 이해가 어려웠다. return 값은 task를 전부 끝내기 위한 최소 소요 시간. 단 task를 수행하는데 있어서 조건이 있는데 하나의 task는 1unit시간에 끝난다. 하지만 같은 task사이엔 무조건 n유닛 이상의 쿨타임이 돌아야 한다.

 

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

 

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B There is at least 2 units of time between any two same tasks.

 

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6

Explanation: On this case any permutation of size 6 would work since n = 0. ["A","A","A","B","B","B"] ["A","B","A","B","A","B"] ["B","B","B","A","A","A"] ... And so on.

 

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2 Output: 16

Explanation: One possible solution is A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

 

Constraints:

• 1 <= task.length <= 104
• tasks[i] is upper-case English letter.
• The integer n is in the range [0, 100].

문제 풀이

- 큐 문제라길래 큐로 풀려하다가 못풀었다...

- 대신 맵을 사용함. 큐 어떻게 쓰는거지

가장 많이 등장한 알파벳을 카운트해서 저장한다. 예를 들어 가장 많이 등장한 문자를 a라 한다면

a X X X

a X X X

a

로 배치하면 된다.  n의 수에 맞게 X가 뭐든 간에 배치하면 된다.

따라서 (max count - 1) * (n + 1) 을 한것이 두 번째 줄 까지의 소요 시간이다.

나머지 남은 테스크는 max count -1보다 크다면 (즉 a와 등장 횟수가 동일하다면) 결과값에 +1해준다.

- 주의할 점: 결과값이 tasks의 사이즈 즉 인풋 사이즈보다 작은 경우... n이 0인 경우가 이에 속한다. 이 땐 task size를 return 해야한다.

- 새로 배운 문법: auto  알아서 타입을 지정해준다. 매우 편리

using namespace std;
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int result;
        
        map<char, int> m;
        
        int maxCnt = 0;
      
        for(int i=0; i<tasks.size(); i++){
            m[tasks[i]]++;
            maxCnt = max(maxCnt, m[tasks[i]]);
        }
        
        result = (n+1)*(maxCnt -1);
        
        for(auto i:m){
            if(maxCnt -1 < i.second){
                result++;
            }
        }
        
        if(result < tasks.size()){
            result = tasks.size();
        }
        return result;
        
    }
};

 

+ 추가 : priority queue사용

map<char, int>는 동일하게 만든다.

sort기준을 int 오름차순으로 한 priorit queue선언. map을 집어 넣는다.

 

수도 코드

while(!q.empty()){
	period = n;
    vector <map> remain;
    while(period > 0 && !q.empty()){
    	map tmp = q.pop();
        tmp.second -= 1;
        remain.push(tmp);
        
        result ++;
        period--;
     }
     
     for(auto i:remain){
     	if(i.second>0) q.push(i);
     }
     
     if(q.empty()) break;
     
     if(period>0) result += break; // 남은 시간은 idle time
 }