[알고리즘문제] 릿코드 Task Scheduler

leetcode.com/problems/task-scheduler/

Task Scheduler - LeetCode

작업 스케줄을 tasks 배열로 인자에 넘겨준다.

배열에는 작업해야 될 task가 주어지며 task는 알파벳 대문자 char로 표현된다.

각 작업에는 cool time이 존재한다.

1time에 1개의 작업만 수행 한다.

한 작업이 수행 된 경우 cool time n시간 동안 해당 작업을 다시 할 수 없다.

 

쿨타임의 존재와 우선순위 계산 때문에 햇갈렸던 문제이다.

우선순위의 존재 때문에 푸는데 시간이 좀 걸렸다.

우선순위는

1. 쿨타임이 존재하지 않고,

2. 작업해야 될 것이 가장 많이 남았으며,

3. 작업한지 가장 오래된 것을 최우선 순위로 두어야 한다.

 

time complexity : O(n^2)

space complexity : O(n)

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>

using namespace std;

class Solution {
private:
    map<char, int> q;
    map<char, int> m;
public:
    int leastInterval(vector<char>& tasks, int n) {
        if (n == 0) return tasks.size();
        sort(tasks.begin(), tasks.end());
        int total = tasks.size();
        for (char c : tasks) {
            m[c]++;   //작업해야 될 갯수를 저장하는 map
            q[c] = 0; //각 작업에 대한 쿨타임을 저장하는 map
        }

        int time = 0;
        while (total) {
            char tmp = ' ';
            time++;
            bool next = false;
            priority_queue<pair<int, char>> pq;
            for (auto it = m.begin(); it != m.end(); it++) {
                //작업해야 될 것이 있는것 && coolTime이 0인것
                if (it->second > 0 && q[it->first] == 0) {
                    //우선순위 계산을 위해 priority_queue에 push
                    pq.push(pair<int, char>(it->second, it->first));
                    next = true;
                }
            }
            if (next == true) {
                char sht = pq.top().second;
                q[sht] = n; //쿨타임을 입력한다.
                m[sht]--;   //작업해야 될 갯수를 감소시킨다.
                tmp = sht;
                total--;
            }
            
            for (auto it = q.begin(); it != q.end(); it++) {
                //방금 저장한 작업 빼고 쿨타임을 감소 시킨다.
                if (q[it->first] > 0 && tmp != it->first) {
                    it->second--;
                }
            }
        }

        return time;
    }
};

 

다른 풀이 방법

가장 숫자가 많이 나온 task의 idle에 다른 task를 넣어주는 방식으로 풀어내는 방법이다.

(maxTask - 1) * (n + 1) + numpeak(가장 숫자가 많은 task의 수 - 1) * (cool time + 1) + 가장 숫자가 많은 task의 수

로 계산을 해준다

maxTask에서 -1을 해주는 이유는 마지막 순서에서 idle을 계산할 필요가 없기 때문이다.

n + 1인 이유는 n개의 idle 다음에 task가 와야 되기 때문이다. 

n이 2라면 A _ _ 다음 A가 와야 되기 때문이다.

가장 숫자가 많은 task의 수가 여러개일 수 있기때문에 numpeak만큼 더해주도록 한다.

class Solution {
private:
    map<char, int> task;
public:
    int leastInterval(vector<char>& tasks, int n) {
        if (n == 0) return tasks.size();
        //tasks중 가장 많은 task가 가장 많은 idle을 만들 수 있다.
        //가장 많이 나온 task로 idle 수를 구한 다음 남은 task들을 idle에 채워 넣는다.
        int maxTask = 0, m = tasks.size();
        int numpeak = 0;

        //가장 숫자가 많은 task에 대한 값을 저장한다.
        for (auto& c : tasks) {
            maxTask = max(maxTask, ++task[c]);
        }

        //가장 숫자가 많은 task의 수를 구한다.
        for (auto& c : task) {
            if (c.second == maxTask) {
                numpeak++;
            }
        }
        //(가장 숫자가 많은 task의 수 - 1) * (cool time + 1) + 가장 숫자가 많은 task의 수
        return max(m,(maxTask - 1) * (n + 1) + numpeak);
    }
};

예를들어 A A A B B B 와 n이 2가 주어졌을 경우

A _ _ A _ _ A를 하고 그 다음 

AB_AB_AB 요렇게 되는것이다,

A A A B B B C C와 n이 2가 주어졌을 경우

A _ _ A _ _ A를 하고 그 다음

AB_AB_AB를 하고 그다음

ABCABCAB를 하는 것 이다. 

 

typescript 코드

function leastInterval(tasks: string[], n: number): number {
    if (n === 0) return tasks.length;

    let maxTask : number = 0;
    let numpeak : number = 0;
    let m : number = tasks.length;
    let task : Object = {};

    for(let i of tasks){
        task[i] = task[i] ? task[i] + 1 : 1;
        maxTask = Math.max(maxTask, task[i]);
    }
    Object.keys(task).forEach(key => {
        if(task[key] == maxTask) numpeak++;
    });

    return Math.max(m, (maxTask - 1) * (n + 1) + numpeak);
};

 

rust 코드

use std::collections::HashMap;
use std::cmp::max;

struct Solution;

impl Solution {
    pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
        if n == 0 { return tasks.len() as i32; }
        let mut max_task = 0;
        let m = tasks.len();
        let mut numpeak = 0;
        let mut task = HashMap::new();
        for c in tasks.iter(){
            if task.contains_key(c){
                *task.get_mut(c).unwrap() += 1;
            }else{
                task.insert(c, 1);
            }
            max_task = max(max_task,task[c]);
        }
        for c in task.iter(){
            if *c.1 == max_task {
                numpeak += 1;
            }
        }

        max(m as i32, (max_task - 1) * (n + 1) + numpeak)
    }
}