[Leetcode/C++] 621_Task Scheduler

문제는 다음과 같습니다.

주어진 문제를 해석하고 문제가 원하는 요건은 다음과 같습니다.
주어진 배열을 나열하되, 주어진 n기간 사이에는 같은 수를 넣을 수 없고, 이 때에는 idle을 넣을 수 있다.

제가 문제를 푼 과정은 다음과 같습니다.

1. 해쉬맵을 이용하여 key와 value로 <알파벳, 해당 알파벳 개수> 로 데이터 1차 가공

2. 해쉬맵에서 value값을 기준으로 내림차순 정렬을 하기 위해 vector<pair<char, int>>로 데이터 2차 가공

3. 우선순위 큐를 이용하여 문제에서 주어진 조건의 답 구하기

맵에서는 sort를 이용할 수 없어서, 1번과 2번 두 번의 과정을 거쳤습니다.

1번의 과정은 다음과 같습니다.

map<char, int> m;
for(int i=0; i<tasks.size(); i++) m[tasks[i]]++;

2번의 과정은 다음과 같습니다.

먼저 사용자정의정렬을 위해, 정렬기준을 따로 설정했습니다.

struct cmp{
    bool operator() (pair<char, int> &x, pair<char, int> &y){
        return x.second < y.second;
    }
};

priority_queue<pair<char, int>, vector<pair<char, int>>, cmp> pq, tmp;
for(auto item: m) pq.push(item);

가장 핵심인 3번의 과정은 다음과 같습니다.

int res=0;
while(!pq.empty()){
    int i;
    for(i=0; i<=n && !pq.empty(); i++){
        if(pq.top().second > 1){
            tmp.push({pq.top().first, pq.top().second-1}); // 재활용 할 것만 tmp에 넣기(개수가 1 이상인 것만)
        }
        res++;
        pq.pop();
    }
    if(i!=n+1 && (pq.empty() && !tmp.empty())) res+=((n+1)-i);
    while(!tmp.empty()){
        pq.push(tmp.top());
        tmp.pop();
    }
} // 전체 while문 끝

먼저 정렬까지 마친 가공된 데이터는 우선순위 큐 pq에 있습니다.
특정 기간 n이 반복문의 주기가 되고(이 사이에서 같은 값이 나오면 안되므로)

이에서 값을 뽑는데
뽑은 값은 결과를 담은 변수 res에 res++; 로 개수를 세고,
객체의 원소 개수는 -1씩 감소됩니다.
이때, 감소된 객체의 수가 1 이상인 것만 임시 우선순위 큐인 tmp에 다시 넣습니다.

한 주기(사이클)이 끝났을 경우,
tmp에 있는 모든 원소를 다시 우선순위 큐 pq에 넣는 과정을 수행합니다.
❗️그리고 이 한 사이클 동안, 객체의 원소를 모두 채우지 못했을 경우❗️
res+=((n+1)-1); 만큼 결과값에 더해 줍니다.
이는, 문제에서 idle을 추가하는 과정과도 같습니다.

전체 코드는 다음과 같습니다.

class Solution {
public:
    struct cmp{
        bool operator() (pair<char, int> &x, pair<char, int> &y){
            return x.second < y.second;
        }
    };
    
    int leastInterval(vector<char>& tasks, int n) {
        map<char, int> m;
        for(int i=0; i<tasks.size(); i++) m[tasks[i]]++;
        
        priority_queue<pair<char, int>, vector<pair<char, int>>, cmp> pq, tmp;
        for(auto item: m) pq.push(item);
        
        int res=0;
        while(!pq.empty()){
            int i;
            for(i=0; i<=n && !pq.empty(); i++){
                if(pq.top().second > 1){
                    tmp.push({pq.top().first, pq.top().second-1}); // 재활용 할 것만 tmp에 넣기
                }
                res++;
                pq.pop();
            }
            if(i!=n+1 && (pq.empty() && !tmp.empty())) res+=((n+1)-i);
            while(!tmp.empty()){
                pq.push(tmp.top());
                tmp.pop();
            }
        } // 전체 while문 끝
        
        
        return res;
    }
};