Url: https://leetcode.com/problems/task-scheduler/description/
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note:
- The number of tasks is in the range [1, 10000].
- The integer n is in the range [0, 100].
생각보다 쉬울 줄 알았는데 두시간 이상 고민했던 문제. 단순히 배열을 tasks.length * n만큼 만들어두고 거기다 A-Z중에 빈도수 가장 높은거부터 채워놓으려고 했는데, 이상하게 딱 하나의 테스트 케이스만 통과하지 못했다.
자세히 보니, 따로 배열 만들어서 거기다 채울 필요 없이 단순 프레임 사이즈 계산으로 답이 나오더라.
public class Solution {
public int leastInterval(char[] tasks, int n) {
int[] c = new int[26];
for(char t : tasks){
c[t – ‘A’]++;
}
Arrays.sort(c);
int i = 25;
while(i >= 0 && c[i] == c[25]) i–;
return Math.max(tasks.length, (c[25] – 1) * (n + 1) + 25 – i);
}
}
모범 답안(?) 이 이렇게 되는데 결국 저 프레임 사이즈인 (c[25] – 1) * (n + 1) + 25 – i가 관건이다. 즉, 모든 알파벳의 빈도수를 세고, 정렬하면 c[25]가 가장 큰 빈도수가 될 것인데, 같은 빈도수가 있다면 c[25]부터 앞으로 올라가면서 같은 빈도수를 찾고, 그게 i값이 될 것이다. 즉, (빈도수 – 1) * (프레임) + (빈도수를 제외한 다른 알파벳의 개수) 가 될 것이다.
사실 사뭇 25 – i가 이해가 되질 않았는데, 단순히 채워놓는 용도. 그리고 내가 간과했던 것은 n이 정적값이 아니라는 사실이다. at least n이지, n만큼을 띄워야 하는 게 아니다. 그래서 최빈도수 문자열로 프레임을 만들어 두고 끼워넣으면 된다. 끼워넣게 되면 그 길이가 tasks.length가 될 것이고, 프레임을 대상으로 하면 위의 공식이 나온다.
정말 문제를 잘 읽어야 겠다는 생각. 여튼 재밌는 문제인 것은 확실하다.
