Task Scheduler

https://ygs3004.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F

티스토리

 

주어지는 Task를 실행하기 위한 시간을 구하는 문제이다. 같은 Task를 실행하기 위해선 n 만큼의 시간이 지나야 한다는 제한 조건이 있다.

 

Task를 실행하기 위하여 반복되는 Task를 우선 실행하게 하기로 했다. PriorityQueue를 이용하여 Task의 repeat을 기준으로 정렬 되도록 하였다. 단 이때 n 만큼의 시간이 더 필요한 경우를 체크해야 했기 때문에 현재 실행이 불가능한 경우는 next로 이동시켜 주었다. 모든 Task가 실행이 불가능한 경우 next로 전부 이동이 되며 while 문이 종료된다. 이 때는 다음 루프로 cnt가 증가하며 idle이 실행된 것으로 간주할 수 있다. 실행 가능한 Task가 있을 경우 해당 task를 poll한 상태로 나머지를 next로 이동시켜 주어서 문제를 해결했다.

import java.util.*;  
  
public class Solution {  
    public int leastInterval(char[] tasks, int n) {  
        PriorityQueue<Task> pq = new PriorityQueue<>();  
        int[] repeats = new int[26];  
  
        // 문자별 반복 횟수 체크  
        for(int i = 0; i < tasks.length; i++){  
            char c = tasks[i];  
            repeats[c - 'A']++;  
        }  
  
        // 문자 반복 및 값 정보 pq 에 삽입,  
        // n의 최대값이 100이므로 초기 lastIdx를 충분히 낮은 값인 -101로 주었다.  
        // Integer.MIN_VALUE 처럼 극한 값을 주면 오버플로우 발생 가능  
        for(int i = 0; i < repeats.length; i++){  
            if(repeats[i] > 0){  
                char c = (char)(i + 'A');  
                pq.add(new Task(repeats[i], c, -101));  
            }  
        }  
  
        int cnt = 0;  
        while(!pq.isEmpty()){  
            PriorityQueue<Task> next = new PriorityQueue<>();  
            cnt++;  
  
            // 실행 할수 있는 Task 가 있는지 확인  
            while(!pq.isEmpty()){  
                Task task = pq.poll();  
                int lastIdx = task.lastIdx;  
                if(cnt - lastIdx > n){  
                    task.lastIdx = cnt;  
                    task.repeat--;  
  
                    if(task.repeat > 0){  
                        next.add(task);  
                    }  
                    break;  
  
                }  
                // Task 가 next로 전부 이동될 동안 실행 불가능할 경우 idle                
                next.add(task);  
            }  
  
            // 나머지 Task next 로 이동  
            while(!pq.isEmpty()){  
                next.add(pq.poll());  
            }  
  
            // next pq를 이용하여 다음 체크  
            pq = next;  
        }  
  
        return cnt;  
    }  
  
    private static class Task implements Comparable<Task>{  
        int repeat;  
        char value;  
        int lastIdx;  
  
        Task(int repeat, char value, int lastIdx){  
            this.repeat = repeat;  
            this.value = value;  
            this.lastIdx = lastIdx;  
        }  
  
        @Override  
        public int compareTo(Task o){  
            return Integer.compare(o.repeat, this.repeat);  
        }  
    }  
}

 

코드를 완성하고 나서 결과가 다른 정답 코드에 비해 느린 편으로 나왔다. 다른 코드의 방식은 규칙성을 이용해 일종의 수학적 공식을 만드는 방식이었다. 하지만 실제 해당 코드에서 task가 진행되는 동안에 추가적인 동작이 필요하다면 이용할 수 없기에 좋은 방법은 아닌듯하다. 수학적인 방식이 아니라 프로그래밍 방식의 해결 방법을 위해서는 PriorityQueue를 쓰는게 좋은 풀이라고 생각한다.