[알고리즘] 최소 실행 시간 구하기

 

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

태스크 스케줄러

문제) You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

 

일단 제일 먼저 생각이 난 것은 각 알파벳의 빈도수를 구하기 위해 맵 혹은 객체의 형태로 정리하는게 좋다고 생각했다.

그리고 무언가 정렬을 해주고, 뽑아내는 우선순위 큐 문제인가 싶은데, 여기서부터 막혀서 GPT의 도움을 받아보기로 했다.

 

결과적으로 복잡하게 정렬을 하고 자시고 할필요도 없이 최소 실행 시간을 구하는 공식이 있다고 했다. 

최소 실행 시간을 구하는 공식
min time = (maxFreq−1) × (n+1) + maxCount
단, 위 계산 결과가 전체 작업 개수보다 작으면 tasks.length를 반환해야 함.

 

그리고 정말 이 공식을 대입해 문제를 풀어보니 잘 풀렸다. 오늘도 수학의 중요성(?)을 깨닫는다.

// 정답 코드

var leastInterval = function(tasks, n) {
    if(n === 0) return tasks.length; 
    let taskMap = new Map();
    tasks.forEach(task => {
        taskMap.set(task, (taskMap.get(task) + 1) || 1);
    })
    
    let maxFreq = Math.max(...taskMap.values());
    let maxCount = 0;
    for(let value of taskMap.values()) {
        if(maxFreq === value) maxCount += 1;
    }
    let answer = (maxFreq - 1) * (n + 1) + maxCount;

    return Math.max(answer, tasks.length);
};