[LeetCode#621] Task Scheduler

 

❒ Description

---

날짜	2024.09.17 (화)
제목	Task Scheduler
링크	https://leetcode.com/problems/task-scheduler/description/
자료구조	배열 & 우선순위 큐
알고리즘	그리디
시간 복잡도	O(NlongN)

 

아이디어도 생각나지 않았던 문제였다.

 

 

 

 

 

❒ 문제 분석

---

이번 문제는 주어진 task를 모두 수행하기 위한 최소 횟수를 출력하는 것이다. 그리고 동일한 task를 수행하기 위해선

주어진 interval을 신경써줘야 한다. 문제에서 변수 `n`을 interval로 제시해준다.

 

예를 들어 interval이 3이라면 동일한 `A` 작업을 마무리하기 위해서는 `A _ _ _ A` 와 같이 3번의 interval이 필요

하다. 여기서 한 가지 규칙을 발견할 수 있다. 한 번의 cycle에서 총 `n + 1`개의 task를 처리할 수 있다는 규칙이다. 

여기서 한 번의 cycle이란 `A _ _`를 의미한다.

 

그리고 빈도수가 가장 많은 task 부터 처리하는 해야 문제의 목적인 최소 횟수 출력이라는 조건을 충족할 수 있다.

 

 

 

 

 

❒ Solution

---

1. 우선순위 큐

public int leastInterval(char[] tasks, int n) {
    int[] freqs = new int[26];
    for (char c : tasks) {
        freqs[c - 'A']++;
    }
    Queue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    for (int freq : freqs) {
        if (freq > 0) {
            pq.add(freq);
        }
    }

    int result = 0;
    while (true) {
        int intervals = 0;
        List<Integer> pendingTasks = new ArrayList<>();
        while (!pq.isEmpty()) {
            int frequency = pq.poll();
            if (intervals < n + 1) {
                intervals ++;
                result ++;
                if (frequency > 1) {
                    pendingTasks.add(frequency - 1);
                }
            } else {
                pendingTasks.add(frequency);
            }
        }
        if (pendingTasks.isEmpty()) {
            break;
        }
        pq.addAll(pendingTasks);
        result += n + 1 - intervals;
    }
    return result;
}

i. Task 빈도 수 배열 생성

int freqs = new int[26];
for (char c : tasks) {
    freqs[c - 'A']++;
}

• 주어진 task의 빈도를 계산한다. (freqs 배열)
• 작업이 'A'라면 freqs[0]에, 'B'라면 freqs[1]에 저장한다.

 

ii ) 우선 순위 큐에 빈도가 1 이상인 값만 내림차순으로 삽입

Queue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
for (int freq : freqs) {
    pq.add(freq);
}

 

 

iii ) Main Logic - 하나의 cycle 동안에 작업 처리

int result = 0;
while (true) {
    int intervals = 0;
    
    // 다음 cycle에 처리할 task를 담을 ArrayList 선언
    List<Integer> pendingTasks = new ArrayList<>();
    
    // PQ가 빌 때 까지 반복
    while (!pq.isEmpty()) {
        int frequency = pq.poll():
    	if (intervals < n + 1) {
            intervals ++;
            results ++;
            if (frequency > 1) {
                pendingTasks.add(frequency - 1);
            }        
        } else {
            pendingTasks.add(frequency);
        }
    }
    
    // 다음 cycle에 작업할 task 없는 경우 while문 break
    if (pendingTasks.isEmpty()) {
        break;
    }
    
    // PQ에 다음 cycle에 처리할 task 삽입
    pq.addAll(pendingTasks);

    // cycle이 끝날 때 n + 1개의 작업이 다 채워지지 않았을 경우, 남은 interval을 추가한다. 
    result += n + 1 - intervals;
}
return result;

 

 

 

2.  최대 빈도 기반으로 idle 시간 계산

public int leastInterval(char[] tasks, int n) {
    int[] freqs = new int[26];
    for (char c : freqs) {
        freqs[c - 'A']++;
    }
    Arrays.sort(freqs);
    int maxFreq = freqs[25] - 1;
    int idle = maxFreq * n;
    for (int i = 24; i >= 0; i--) {
        idle -= Math.min(maxFreq, freqs[i]);
    }
    return idle > 0 ? idle + tasks.length : tasks.length;
}

두 번째 풀이는 최대 빈도 task 기준으로 풀이한 코드이다. 가장 빈도가 높은 작업의 빈도에서 1을 뺀 값을 기반으로

나머지 작업이 얼마나 채워질 수 있는지 계산한다. 

 

 

3. 공식 사용...? 

public int leastInterval(char[] tasks, int n) {
    int[] freqs = new int[26];
    for(char c: tasks) {
        freqs[c - 'A']++;    
    }

    int maxFreq = 0;
    int maxCount = 0;
    for(int freq : freqs) {
        if(freq > maxFreq) {
            maxFreq = freq;
            maxCount = 1;
        }
        else if(freq == maxFreq) {
            maxCount++;
        }
    }
    int minIntervals = (maxFreq-1) * (n+1) + maxCount;
    return Math.max(minIntervals, tasks.length);
}

이 풀이는 최소 간격을 구하는 공식을 사용한 풀이로 보인다.

※ 공식 : (maxFreq - 1) x (n + 1) + maxCount 

 

 

 

 

 

 

---