프로그래머스 level2 : 과제 진행하기 - Java

.

 

생각해야할 경우의 수가 많았던 문제이다.

과제(Task) 클래스를 하나 만들어서 PriorityQueue와 Stack 을 사용하면 수월하게 풀수 있다. 

PriorityQueue말고 Arrays를 써서 정렬해서 써도된다

 

 

import java.util.*;

class Solution {
    
    static class Task{
        private String name;
        private int start;
        private int playtime;
        
        public Task(String name, int start, int playtime){
            this.name = name;
            this.start = start;
            this.playtime = playtime;
        }
        
        public Task(String name, int playtime){
            this.name = name;
            this.playtime = playtime;
        }
    }
    
    public List<String> solution(String[][] plans) {
        List<String> answer = new ArrayList<>();
        
        // 해야할 과제들을 시간순으로 저장 - Task의 start 오름차순으로 정렬
        PriorityQueue<Task> pq = new PriorityQueue<>(
            (o1, o2) -> ( o1.start - o2.start )
        );
            
        // 과제들의 시작시간들을 분으로 환산하여 Task로 생성하여 pq에 넣음
        for(int i = 0; i < plans.length; i++){
            String[] start = plans[i][1].split(":");
            int hour = Integer.parseInt(start[0]);
            int minute = Integer.parseInt(start[1]);
            
            pq.add(new Task(plans[i][0], hour*60 + minute, Integer.parseInt(plans[i][2])));
        }
        
        // 잠시 멈춘 과제들을 저장 - 최근것부터 꺼내서 하기때문에 Stack 사용.
        Stack<Task> pauseStack = new Stack<>();
        
        // 지금과 다음 과제의 시간 차를 사용해서 반복하며
        // 지금 과제를 끝내기 or 멈춘 과제 stack에 넣기 를 수행
        while(!pq.isEmpty()){
            Task curTask = pq.poll();
            
            String curName = curTask.name;
            int curStart = curTask.start;
            int curPlaytime = curTask.playtime;
            
            int curTime = curStart;
            
            // 남은 새로운 과제가 있다면..
            //  1. 지금 과제끝내고 시간이 남는 경우
            //  2. 지금 과제 끝내고 시간이 안남는 경우
            //  3. 지금 과제를 끝내지 못하는 경우 
            if(!pq.isEmpty()){
                Task nextTask = pq.peek();
                int nextStart = nextTask.start;
                
                // 1. 지금 과제끝내고 시간이 남는 경우
                if(curStart + curPlaytime < nextStart){
                    answer.add(curName);
                    curTime += curPlaytime;
                    
                    int leftTime = nextStart - curTime;
                    
                    // 멈춘 과제 있으면 꺼내서 남은시간동안 하기
                    while(!pauseStack.isEmpty()){
                        Task pauseTask = pauseStack.pop();
                        
                        // 다음 과제 시작전 다 끝낼 경우
                        if(pauseTask.playtime <= leftTime){
                            curTime += pauseTask.playtime;
                            answer.add(pauseTask.name);
                            leftTime -= pauseTask.playtime;
                            continue;
                        }
                        
                        // 다음 과제 시작 전 다 끝내지 못할 경우
                        else{
                            int pt = pauseTask.playtime - leftTime;
                            pauseStack.push(new Task(pauseTask.name, pt));
                            break;
                        }
                    }
                }
                
                // 2. 지금 과제 끝내고 시간이 안남는 경우
                else if(curStart + curPlaytime == nextStart){
                    answer.add(curName);
                    continue;
                }
            
                // 3. 지금 과제를 끝내지 못하는 경우
                else{
                    int leftTime = curPlaytime - (nextStart - curTime);
                    pauseStack.push(new Task(curName, leftTime)); 
                }
            }
            
            // 남은 새로운 과제가 없다면..
            // 1. 멈춘 과제도 없는 경우
            // 2. 멈춘 과제가 있는 경우
            else{
                
                // 1. 멈춘 과제도 없는 경우
                if(pauseStack.isEmpty()){
                    answer.add(curName);
                    curTime += curPlaytime;
                }
                
                // 2. 멈춘 과제가 있는 경우
                else{
                    answer.add(curName);
                    while(!pauseStack.isEmpty()){
                        Task ps = pauseStack.pop();
                        curTime += ps.playtime;
                        answer.add(ps.name);
                    }
                }
            }
        }
        
        return answer;
    }
}