621. Task Scheduler

leetcode.com/problems/task-scheduler/submissions/

Task Scheduler - LeetCode

접근법

그리디한 문제

 

해석.

같은 업무일 경우 최소 N만큼 떨어져 있어야한다.

 

["A","A","A","B","B","B"], n = 2인 경우

 

A B _ A B _ A B 처럼 업무를 처리해야한다.

 

풀이

1) 가장 많이 나오는 알파펫 파악

2) idle을 감소

 

먼저 가장 많이 나오는 문자를 구해야한다.

 

A _ _ A _ _ A 이런 틀을 만들 수 있다.

 

이제, ' _ ' 이 빈 문자열을 idle이라고 하겠다. 

 

B가 나올수 있는 곳은 빨간 네모칸 하나당 한개만 들어가는게 가능.

그래서 우리는 업무를 탐색하면서 저 idle의 갯수를 줄여주면 된다.

 

즉, Math.min(A의 출현갯수, i 업무의  출현수) 가 업무가 idle자리에 들어갈 수 있는 갯수가된다.

 

위의 예시에서는 B의 갯수니깐 2가 된다

 

탐색을 전부 끝내고, tasks의 길이 + 업무의 길이가 된다.

 

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int al[] = new int[26];
        int max=0;
        int idx=0;
        for(char task: tasks){
            al[task-'A']++;
            if(al[task-'A'] > max){
                max =   al[task-'A'];
                idx = task-'A';
            }
        }
        int plus=0;
        int idle = (al[idx]-1)*n;
        for(int i=0; i<26; i++){
            if(idle==0) break;
            if(al[i]==0 || i==idx) continue;
            int tmp = Math.min(max-1, al[i]);
            idle-= tmp;
            if(idle<0){
                plus = Math.abs(idle);
                break;
            }
        }
        int answer = idle+tasks.length+plus;
        return answer;
    }
}