Task Scheduler

분명히 풀어 본 기록은 있는데 언제 풀었는지 가물가물 해서 기록을 보니 2020년에 풀어봤다.

2020년의 코드는 내가 어떻게 할 줄 몰라서 다른 사람의 코드를 보고 적었는데 몇년이 지난 지금은그냥 보고 머리 속에 구성하고 슥슥 풀었다.

사실 이게 베스트 답은 아니지만, 문제를 보고 무조건 그리디하게 PQ를 사용해서 풀어야 한다고 느꼈다. 첫번 째 등장하는 알파벳은 1순위로 만들고 그 다음에 오는 알파벳은 첫번 째 순서를 기준으로 + 해주었다.

그리고 시간을 정해서 만약에 돌릴 수 있는 시간이면 pop을, 안된다면 그냥 시간만 ++ 해주는거로 풀 수 있었다.

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int answer = 1; 
        sort(tasks.begin(), tasks.end()); 
        map<char,int> hashMap; 
        priority_queue<int, vector<int>, greater<int>> pq; 
        for(int i = 0; i < tasks.size(); i++){
            if(hashMap.count(tasks[i])){
                hashMap[tasks[i]] = hashMap[tasks[i]] + n + 1; 
                pq.push(hashMap[tasks[i]]); 
            } else{
                hashMap[tasks[i]] = 0; 
                pq.push(0); 
            }
        }

        while(!pq.empty()){
            int top = pq.top(); 
            if(answer > top){
                pq.pop(); 
                answer++;
            } else{
                answer++; 
            }
        }


        return answer -1; 
    }
};