Gidhub BE Developer

LeetCode : 621. Task Scheduler

2021-11-07
goodGid
LeetCode

621. Task Scheduler

Problem

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.

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.

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

Example

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

[1] Code (21. 11. 07)

Need to Retry

n/a

Concern Point

자료구조 선택

LinkedList로 접근을 하려 했으나 적절하지 않았다.
정답 코드들을 보니 
그냥 배열 값으로만 처리하거나
우선순위 큐를 사용하는 코드가 많이 보였다.

Reference Code

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int len = tasks.length;
        int[] arr = new int[26];

        for (int i = 0; i < len; i++) {
            arr[tasks[i] - 'A']++;
        }

        int max = arr[0];
        int count = 0;

        for (int i = 0; i < 26; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        for (int i = 0; i < 26; i++) {
            if (max == arr[i]) {
                count++;
            }
        }
        return Math.max(len, (max - 1) * (n + 1) + count); // [1]
    }
}
  • [1] : len 값을 비교해주는 이유는 다음 예시를 보면 된다.
["A","A","A","B","B","B"]
0

return (max - 1) * (n + 1) + count);

위 코드로 실행하면 "4"가 나온다.
하지만 실제로는 "6"이 정답이다.

idx : 1 2 3 4 5 6
val : A B A B A B

Review

  • 아이디어를 떠올리는 데 실패했다.

[2] Code (22. 01. 07)

Need to Retry -> 아이디어는 맞았으나 구현에서 실패

// Wrong Code
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] alpha = new int[26];
        int size = tasks.length;

        if (n == 0) {
            return size;
        }

        int maxCnt = 0;
        for (char c : tasks) {
            alpha[c - 'A']++;
            maxCnt = Math.max(maxCnt, alpha[c - 'A']);
        }

        int cnt = 0;
        for (int i = 0; i < alpha.length; i++) {
            if (maxCnt == alpha[i]) {
                cnt++;
            }
        }

        cnt += (maxCnt - 1) * (n + 1);

        int subSize = size - maxCnt;

        if ((maxCnt - 1) * (n + 1) < subSize) {
            cnt += subSize - ((maxCnt - 1) * (n + 1));
        }

        return cnt;
    }
}

Reference Code

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int len = tasks.length;
        int[] arr = new int[26];

        for (int i = 0; i < len; i++) {
            arr[tasks[i] - 'A']++;
        }

        int max = arr[0];
        int count = 0;

        for (int i = 0; i < 26; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        for (int i = 0; i < 26; i++) {
            if (max == arr[i]) { // [1]
                count++;
            }
        }
        return Math.max(len, (max - 1) * (n + 1) + count); // [2]
    }
}

  • [1] : [“A”,”A”,”B”,”B”] 와 같은 경우를 위해 필요한 코드이다.

  • [2] : len 값을 비교해주는 이유는 다음 예시를 보면 된다.

["A","A","A","B","B","B"]
0

return (max - 1) * (n + 1) + count);

위 코드로 실행하면 "4"가 나온다.
하지만 실제로는 "6"이 정답이다.

idx : 1 2 3 4 5 6
val : A B A B A B

Review

  • 다음엔 꼭 맞추자 !

Reference

Recommend

Index