[C++] LeetCode : Task Scheduler

Question

Task Scheduler

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.

char type의 원소로 이루어진 task배열이 주어진다. 배열의 각 task들은 CPU가 해야 하는 일이며, 각각의 letter는 각기 다른 task들을 나타낸다.
Task 들은 어떠한 순서로도 수행될 수 있으며, 각 task들은 1의 단위 시간에 수행된다.

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.

하지만, 추가로 양의 정수 n이 주어지는데, 이 n은 CPU가 한 task를 처리한 후, 같은 task를 재 처리할 때 필요한 시간을 나타낸다.
예를 들어, A라는 task를 처리했다면, A라는 task를 다시 처리하는데 최소 n만큼의 시간이 필요하다는 뜻이다.

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

모든 task들을 처리하는데 필요한 최소한의 단위 시간을 return 하라.


제약사항

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

---

Solution

문제를 풀 때 고려한 사항

• task는 영어 대문자로 주어진다. 영어 소문자는 고려할 필요가 없다.
• n이 0일 때 알고리즘이 잘 동작하는지 봐야 한다.

---

Solution1

가장 쉽게 생각할 수 있는 방법은 그저 시뮬레이션을 돌리는 것이다.
task는 알파벳 대문자로만 주어지기 때문에 task와 cool down시간을 저장할 26개의 공간을 할당하고.
task를 처리하기 위한 queue를 두어, cool down시간을 고려하여 task를 처리를 해준다.
여기에 최소 시간까지 고려한다면, 모든 경우의 수를 loop로 돌려 최소 시간인지를 판단해야 한다.

다만 이 방법은 모든 경우의 수에 대해 해 보는 것이기 때문에 성능이 좋지 않을 것이다.

Solution2

어쨌든 최소 시간으로 처리할 수 있는 방법은 자주 등장하는 task를 먼저 처리해주는 방법이다. 만약 task A가 자주 등장하는 task라면, task A가 실행된 후 n타임이 흐른 후, 또다시 처리해야 하는 task A를 바로 처리해주는 방법이다.
즉, tasks 배열을 돌아 처리해야 하는 task들의 수를 모두 count 한 다음, 같은 task가 많은 순으로 우선순위로 두고 먼저 배치해주는 것이다.

예를 들어, 아래와 같은 tasks들이 있을 때, task가 많은 순으로 처리했을 때와, 임의의 순서로 처리했을 때의 차이이다.

['A', 'A', 'A', 'B', 'B', 'C']

task가 많은 순서 : 'A'=>'B'=>'C'=>'A'=>'B'=>idle=>'A'  (7 : 최소 시간이다)
임의의 순서      : 'B'=>'C'=>'A'=>'B'=>idle=>'A'=>idle=>idle=>'A'  (9 : 임의의 순서로 하면 오래걸린다)

이 방법은 직접 스케쥴링을 하여 배치하는 방법이고, 그렇게 동작하는 코드가 필요하다.

Solution3

위의 논리 과정을 잘 살펴봤을 때, 한 종류의 task를 모두 처리하려면 다른 task의 수와 상관없이 cool_down이 필요한 시간은 동일하다.

즉, 한 종류의 task입장으로 보면, 그 cool_down시간에 다른 task를 처리하냐 idle time으로 가냐의 차이로 볼 수 있다. 이러한 관점에서 보았을 때 최소 시간은, 가장 많이 있는 종류의 task의 수에 따라 결정이 된다.

예를 들어, task 배열에서 'A' task를 총 5번 처리를 해야 하고, n이 2라면,

'A' -> [] -> [] -> 'A' -> [] -> [] -> 'A' -> [] -> [] -> 'A' -> [] -> [] -> 'A'

이런 식으로 진행이 될 것이고 [] 안에는 다른 task혹은 idle time 이 될 것이다.

정리하자면, 한 종류의 task의 입장에서 최소 시간은 아래와 같은 수식을 도출할 수 있다.

((task의 처리 시간) + (idle 시간 n)) * (최다 task의 수 - 1) + (마지막 최다 task)

즉 위의 예를 든 경우라면,
(1 + 2) * (5-1) + 1 = 최소 13시간이다. 하지만, 위의 경우에서 []의 공간은 8개이고, 만약 다른 task가 8개보다 많다면 추가 시간이 필요하다.
식을 수정한다면,

((task의 처리 시간) + (idle 시간 n)) * (최다 task의 수 - 1) + (마지막 최다 task)
+ (다른 task 처리 시간의 합 - ((idle 시간 n) * (최다 task의 수 - 1)))

이 될 것이다. '다만 추가된 식이 0보다 작을 때는 더해줄 필요가 없다'

---

모든 경우의 수가 해결된 것 같다. 하지만, 처리해야 하는 최다 task 수 들의 종류가 여러 개일 때는 어떻게 할까? 예를 들어, task 배열에서 'A' task가 5번, 'B' task가 5번 등장하고, n이 2라면

'A' 'B' [] 'A' 'B' [] 'A' 'B' [] 'A' 'B' [] 'A' 'B'

이런 식으로 진행하는 것이 최소가 될 것이고, 위의 식은 수정되어야 한다.
즉, 다시 정리하자면 식은

((task의 처리 시간) + (idle 시간 n)) * (최다 task의 수 - 1) + (마지막 최다 task)
+ (다른 task 처리 시간의 합 - ((idle 시간 n) * (최다 task의 수 - 1)))
=>
((task의 처리 시간) + (idle 시간 n)) * (최다 task의 수 - 1) + (최대 task 종류의 수)
+ (다른 task 처리 시간의 합 - ((idle 시간 n - 최다 task의 종류의 갯 수) * (최다 task의 수 - 1))) 가 최종식이 될 것이다.

여기서 주의할 부분은, '(idle 시간 n - 최다 task의 종류의 갯 수)'가 0보다 작거나 같을 때는
((idle 시간 n - 최다 task의 종류의 갯 수) * (최다 task의 수 - 1))) 해당 부분이 무의미하다는 것이다. 즉 0으로 처리해줘야 한다.

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
		vector<int> count_task(26, 0);
		
		int max_task_number = 0;
	
		for(auto task : tasks){
			count_task[task-'A']++;
			if(count_task[task-'A'] > max_task_number){
				max_task_number = count_task[task-'A'];
			}
		}
		
		int max_task_type_number = 0;
		int other_task_sum = 0;
		
		for(int i=0; i<26;i++){
			if(count_task[i] == max_task_number){
				max_task_type_number++;
			}else{
				other_task_sum += count_task[i];
			}
		}
		
		
		if(other_task_sum - ((n+1-max_task_type_number) * (max_task_number - 1)) >= 0){
			return (1+n) * (max_task_number-1) + max_task_type_number + other_task_sum - ((n+1-max_task_type_number) * (max_task_number - 1));
		}else{
			return (1+n) * (max_task_number-1) + max_task_type_number;
		}
	
    }
};

• Time complexity : O(n)
• Space Complexity : O(1)

풀고 나니 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 처리를 해결했지만.. 식이 굉장히 복잡하다.
이를 리팩터링을 살짝 해준다면 아래와 같을 순 있는데, 가독성이 좋은지는 모르겠다.

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
		vector<int> count_task(26, 0);
		
		int max_task_number = 0;
	
		for(auto task : tasks){
			count_task[task-'A']++;
			if(count_task[task-'A'] > max_task_number){
				max_task_number = count_task[task-'A'];
			}
		}
		
		int max_task_type_number = 0;
		int other_task_sum = 0;
		
		for(int i=0; i<26;i++){
			if(count_task[i] == max_task_number){
				max_task_type_number++;
			}else{
				other_task_sum += count_task[i];
			}
		}
        
        int ans = (1+n) * (max_task_number-1) + max_task_type_number; 
		int remain_task_num = other_task_sum - ((n+1-max_task_type_number) * (max_task_number - 1));
		
		ans += remain_task_num >= 0 ? remain_task_num : 0;
        
	    return ans;
    }
};

Solution4

Discuss를 보다가 기가 막힌 풀이 방법이 나와서 추가해준다.

class Solution {
public : 
	int leastInterval(vector<char>& tasks, int n) {
		unordered_map<char, int> my_mpa;
		int count = 0;
		for(auto task : tasks) { 
			my_map[task]++;
			count = max(count, my_map[task]);
		}

		int ans = (count - 1) * (n + 1);
		for(auto task : my_map) if(task.second == count) ans++;
		return max((int)tasks.size(), ans);
	}
}

로직의 핵심은 같지만, 마지막 라인이 굉장히 깔끔했다.
가장 많은 수의 task를 기준으로 계산을 하고, 또한 가장 많은 수의 task가 여러 개라면 그 수만큼 추가해주는 부분은 동일한데, 만약 Idel 타임에 들어갈 공간이 Task 수 보다 적다면, 단순히 그 Task전체 사이즈를 Return 하면 되는 것이었다. 잘 생각해보면 당연한 건데 왜 빙빙 꼬아서 코드를 구현했는지 모르겠다.

추가로 STL의 size함수는 Return 타입이 부호가 없는 정수이기 때문에 Int로 타입 캐스팅해주어야 한다.


출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/826/

Explore - LeetCode