.leetcode(621. Task Scheduler)

문제

https://leetcode.com/problems/task-scheduler/

문제 풀기 전

1. 영어 알파벳 대문자로 제한되므로 배열을 쓸 수 있겠다.
2. 제일 많은걸 찾아서 기준을 잡아야겠다.
3. 제일 많은것들이 여러개일때를 고려해야겠다.
4. 제일 많은 것을 기준으로 세웠을때 나오는 빈공간의 수와 남아있는 수를 비교해야겠다.

직접 푼 풀이

소요시간: 37분(22:00 ~ 22:37)

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] alphabets = new int[26];

        for (int i=0; i<tasks.length; i++) {
            alphabets[tasks[i]-'A']++;
        }

        int max = 0;
        int count = 1;
        int total = 0;
        for (int i=0; i<26; i++) {
            total += alphabets[i];
            if (max < alphabets[i]) {
                max = alphabets[i];
                count = 1;
            } else if (max == alphabets[i]) {
                count++;
            }
        }
        if (count <= n+1) {
            int vacant = n*(max-1)- (count-1)*(max-1);
            int remain = total - max*count;
            if (vacant >= remain) {
                return max * (n+1) - n + count -1;    
            } else {
                return max * (n+1) - n + remain -vacant + count -1;
            } 
        } else {
            return tasks.length;
        }
    }
}

느낀점

1. 좀 더 차분하게 풀었으면 마지막 판단의 순간을 더 간결하게 정리해볼 수 있었을 것이다. 아래처럼 말이다.
2. greedy하게 빈공간을 없애볼 수도 있을것이다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] alphabets = new int[26];

        for (int i=0; i<tasks.length; i++) {
            alphabets[tasks[i]-'A']++;
        }

        int max = 0;
        int count = 1;
        int total = 0;
        for (int i=0; i<26; i++) {
            total += alphabets[i];
            if (max < alphabets[i]) {
                max = alphabets[i];
                count = 1;
            } else if (max == alphabets[i]) {
                count++;
            }
        }

        return Math.max(tasks.length, (max-1)*(n+1) + count);
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• greedy하게 풀어보기