[Grind75-LeetCode] Task Scheduler JAVA

반응형

728x90

[Grind75-LeetCode] Task Scheduler - Medium 

---

접근

• 그리디

---

풀이

작업 스케줄러라는 문제로 주어지는 작업을 CPU가 처리하는데 몇 번의 인터벌이 필요한지 구하는 문제이다. 알파벳 대문자로 주어지는 작업이 들어있는 배열과 정수 n이 주어지는데 한 작업은 n의 시간이 지난 뒤에 다시 처리할 수 있는 규칙이 있다. n = 2라면 작업 A가 처리되고 2라는 시간이 흐른 뒤에 다시 처리가 가능해진다는 뜻이다. 1번째에 A가 처리되었다면 2 턴이 지나고 4번째부터 다시 처리가 가능하다. 

 

문제의 설명에서와 예제에서 작업이 배열로 주어지지만 배열 순서에 상관없이 작업 처리가 가능하다고 나와있었다. 그렇다면 처리해야 할 횟수가 많은 작업을 적재적소에 배치하는 것이 중요한데 n이라는 쿨다운 시간이 존재해 처리 횟수가 많은 작업을 우선으로 실행해야 할 것이다. 그래서 작업을 모두 세어 횟수를 저장한 뒤 우선순위 큐에 넣어 처리를 하며 처리한 작업을 쿨다운 맵을 따로 만들어 관리를 해야 하나? key를 n으로 주고 value에 처리한 작업들을 넣어 한 차례마다 1씩 감소를 시켜야 하는 건가 하며 생각을 했지만 n의 범위는 100까지로 시간 초과에 메모리 사용량이 엄청날 것으로 다른 방법을 생각해야 했다. 

 

생각을 해보니 굳이 작업의 이름은 가져갈 필요가 없었다. 작업의 횟수만 세어 우선순위 큐에 넣어준다면 어쨌든 그 고유의 횟수들이 작업을 뜻하는 것으로 처리량이 많은 작업부터 n + 1개씩 꺼내 처리를 해준다면 자체적으로 쿨다운 관리가 가능한 거 같았다.

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

        for (char task : tasks) {
            taskMap[task - 'A']++;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int t : taskMap) {
            if (t > 0) {
                pq.offer(t);
            }
        }

우선 횟수를 저장하고 그 횟수를 토대로 우선순위 큐에 넣어주는 작업이다. 처음에 Map을 사용해 횟수를 세려다 알파벳이고 기본적으로 char 값으로 주어지다 보니 배열을 통해 간단하게 개수를 세어주었다.

	int result = 0;  

        while (!pq.isEmpty()) {
            List<Integer> temp = new ArrayList<>();

            for (int i = 0; i <= n; i++) {
                if (!pq.isEmpty()) {
                    temp.add(pq.poll());
                }
            }
            
            for (int count : temp) {
                if (count - 1 > 0) {
                    pq.offer(count - 1);  
                }
            }
            
            result += pq.isEmpty() ? temp.size() : n + 1;
        }

        return result;
    }

작업을 처리하는 과정이다. 작업은 n + 1개씩 횟수가 많은 순으로 처리된다. n + 1개씩 처리하는 이유는 n 개씩 처리할 경우 앞서 처리된 작업의 쿨다운이 끝나지 않아 다시 바로 처리가 불가능하기 때문이다. 그렇기 때문에 큐에서 n + 1개의 작업을 뽑아준 뒤 temp 리스트에 넣고 처리할 작업들의 횟수를 줄여 처리하고 아직 처리 횟수가 남아있다면 다시 큐에 넣는다. 그리고 마지막 부분이 n + 1 처리를 직접적으로 하는 부분인데 만약 현재 큐가 비었다면 temp의 크기만큼 인터벌 횟수를 증가시킨다. 이 말은 처리할 작업을 방금 마무리를 지어 큐가 비었기 때문에 방금 처리한 작업의 수만큼 횟수를 증가시키는 것이다. 그리고 큐가 비어있지 않다면 아직 처리해야 할 작업들이 남았다는 뜻으로 n + 1만큼 횟수를 더해준 뒤 다시 처리를 수행한다. 만약 n = 2이고 처리해야 할 작업의 종류가 2가지일 경우 확실히 이해할 수 있다. 작업 A, B가 각각 처리되고 난 뒤 처리한 작업의 수인 2만큼 인터벌을 증가시킬 경우 그다음 3번째 처리에서 A과 B가 모두 쿨다운 상태로 처리가 불가능하다. 그렇기 때문에 n + 1을 증가시켜 처음 처리되었던 A의 처리가 다시 가능하게 만들어 쿨다운이 필요한 경우 쿨다운 횟수까지 처리 횟수와 함께 증가시켜 주는 것이다. 

그리디

---

빈자리 계산

성능 좋은 코드들이 많기 때문에 찾아봤더니 성능이 제일 좋은 코드는 평균시간 조작 코드가 있었지만 그 부분을 제거해도 역시나 좋은 성능이었기 때문에 가져왔다. 이렇게 생각을 할 수도 있구나 하는 코드로 제일 처리를 많이 해야 하는 작업 처리 횟수에 n을 곱하여 해당 작업이 처리되지 못하는 쿨다운 시간에 나머지 작업들을 채워 넣는 방식이었다.

    public static int leastInterval(char[] tasks, int n) {
        
        int freq[] = new int[26];

        for(char task : tasks){
            freq[task - 'A']++;
        }

        Arrays.sort(freq);

횟수를 구하고 내림차순으로 등장 횟수를 정렬해 주는 과정이다. 

	int spots = freq[25]  - 1;
        int idleSpots = spots * n;

        for(int i = 24; i >= 0 ; i--){
            idleSpots -= Math.min(freq[i], spots);
        }

제일 횟수가 많은 작업에 n을 곱하는 과정이다. 예를 들어 n = 2이고 A라는 작업이 3으로 횟수가 제일 많다면 -1을 한 뒤 n을 곱해준다. 현재 A는 총 3번의 처리가 필요하여 1번째, 4번째, 7번째에 처리될 수 있다. 그렇기 때문에 다른 작업이 처리될 수 있는 경우는 A의 쿨다운 시간인 2,3,5,6 번째나 7번째 이후에 처리가 가능하다. 만약 2,3,5,6 번째에 다른 작업이 모두 처리가 가능하다면 제일 많은 작업인 A가 마지막으로 처리되는 시간이 최소 횟수가 되고 그 사이의 처리 가능 공간은 아까 계산했던 (3-1) x 2의 값인 4와 동일하다. 그렇기 때문에 남은 다른 작업들로 빈자리를 채울 수 있는지 체크하게 된다. Math.min이 사용되는 이유는 25번 인덱스로 제일 큰 값을 골랐지만 그 값과 동일한 값들이 존재할 수 있기 때문에 spots와 비교해 더 작은 횟수로 채워지게 된다. 예를 들어 A가 3, B가 3으로 횟수가 동일할 때 A가 1, 4, 7번째에 처리가 되고 빈자리는 2,3,5,6이지만 B 또한 쿨다운이 존재해 2,3,5,6 내에 다 채워질 수 없다. 그렇기 때문에 2번만 채워지게 되고 나머지는 7번째 이후에 처리되게 된다.

	if(idleSpots > 0){
            return tasks.length + idleSpots;
        }
        return tasks.length;
    }
}

남은 처리 과정이다. 빈자리가 남아있는 경우 기존 작업의 개수에 빈자리를 더해주게 된다. 빈자리가 남았다는 것은 위의 경우처럼 B가 A처리가 끝난 뒤 8번째에 처리가 되어야 하는 경우나 한 가지 작업이 너무 많아 중간중간 쿨다운 시간을 추가해 주는 것과 같은 의미이다. 두 경우 모두 중간에 대기시간이 포함되어 원래 작업의 횟수보다 많은 처리 시간이 걸린 경우로 대기시간을 추가해 주는 과정이라고 생각하면 된다. 만약 빈자리가 남아있지 않다면 작업들이 대기시간 없이 다 처리되었다는 뜻으로 작업의 길이를 그대로 반환하게 된다. 

빈자리 계산

 

---

전체 코드

그리디

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

        for (char task : tasks) {
            taskMap[task - 'A']++;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int t : taskMap) {
            if (t > 0) {
                pq.offer(t);
            }
        }

        int result = 0;  

        while (!pq.isEmpty()) {
            List<Integer> temp = new ArrayList<>();

            for (int i = 0; i <= n; i++) {
                if (!pq.isEmpty()) {
                    temp.add(pq.poll());
                }
            }
            
            for (int count : temp) {
                if (count - 1 > 0) {
                    pq.offer(count - 1);  
                }
            }
            
            result += pq.isEmpty() ? temp.size() : n + 1;
        }

        return result;
    }
}

 

빈자리 계산

class Solution {

    public static int leastInterval(char[] tasks, int n) {
        
        int freq[] = new int[26];

        for(char task : tasks){
            freq[task - 'A']++;
        }

        Arrays.sort(freq);
        int spots = freq[25]  - 1;
        int idleSpots = spots * n;

        for(int i = 24; i >= 0 ; i--){
            idleSpots -= Math.min(freq[i], spots);
        }

        if(idleSpots > 0){
            return tasks.length + idleSpots;
        }
        return tasks.length;
    }
}