분명히 풀어 본 기록은 있는데 언제 풀었는지 가물가물 해서 기록을 보니 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;
}
};