[프로그래머스] 과제 진행하기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/176962

이 문제는 우선 순위 큐와 스택을 이용하여 문제 조건을 하나하나 구현해나가면 풀 수 있습니다. 이 문제의 조건이 굉장히 복잡하기 때문에 단순하게 생각하고 접근하다가는 꼬여 쉽게 풀 수 없게 됩니다. 따라서 차근차근 조건을 구현하는 능력을 길러야 합니다.

이 문제는 조건을 구현함과 동시에 현재 시간 업데이트 역시 매우 중요합니다. 우선 시간 빠른 순으로 정렬하기 위해 우선 순위 큐를 이용하여 시간값을 정렬합니다. 이 때 계산 편의를 위해 분 단위로 시간을 변환합니다. 우선 순위 큐에서 과제를 하나씩 뽑아내면서 1) 새로운 과제가 더 있는지 를 체크합니다. 만약 있을 경우 1-1) 다음 과제 정보를 가져오고 없을 경우 1-2) 현재 과제를 수행한 다음 멈춘 과제가 존재할 경우 멈춘 과제를 순서대로 수행합니다. 이 때 멈춘 과제는 가장 최근에 멈춘 과제 순으로 수행되기 때문에 스택을 사용하여 저장합니다.

이어서 새로운 과제가 더 있는 경우 2) 새로운 과제 수행 시간 전에 기존 과제를 끝낼 수 있는지 여부를 체크합니다. 만약 2-1) 새로운 과제 수행 시간 전에 기존 과제를 끝내고도 시간이 남는다면 현재 과제 정보를 정답에 추가한 후 현재 시간을 현재 과제 수행 시간만큼 더한 후 멈춘 과제를 탐색합니다. 만약 2-2) 기존 과제를 끝냈을 때 곧바로 새로운 과제 수행 시간이 되었다면 현재 과제 정보를 정답에 추가한 후 현재 시간을 과제 수행 시간만큼 더한 후 곧바로 다음 과제를 진행합니다. 만약 2-3) 과제를 새로운 과제 수행 시간 전까지 수행할 수 없다면 다음 과제 시작 시간과 현재 시간과의 차이만큼 수행시간을 감소시켜 스택에 저장합니다.

2-1)에서 멈춘 과제를 탐색할 때 3) 멈춘 과제를 남은 시간 내에 수행할 수 있는지를 확인합니다. 만약 3-1) 남은 시간 내에 수행 가능하다면 멈춘 과제를 정답에 추가한 후 현재 시간을 최신화합니다. 만약 3-2) 남은 시간 내에 과제를 수행할 수 없다면 수행 시간을 다음 과제 시간에서 현재 시간의 차이만큼 감소시켜 스택에 저장합니다. 여기서 주의할 점은 남은 시간 내에 과제를 여러 개 수행할 수 있기 때문에 반복문으로 처리하며 3-2)에 도달할 경우 break로 빠져나오면 되겠습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static int CURR_TIME = 0;
    
    public List<String> solution(String[][] plans) {
        List<String> answer = new ArrayList<>();
        PriorityQueue<Homework> queue = new PriorityQueue<>();
        Stack<Homework> stack = new Stack<>();
        
        for(String[] plan : plans){
            String name = plan[0];
            int start = calTime(plan[1]);
            int playtime = Integer.parseInt(plan[2]);
            
            queue.add(new Homework(name,start,playtime));
        }
        
        while(!queue.isEmpty()){
            Homework curr = queue.poll();
            CURR_TIME = curr.time;
            
            // 만약 새로운 과제가 더 남아있다면
            if(!queue.isEmpty()){
                Homework next = queue.peek();
                
                // 만약 다음 과제 시작 전까지 과제를 끝내고 시간이 남는다면
                if(next.time > CURR_TIME + curr.playtime){
                    answer.add(curr.name);
                    CURR_TIME += curr.playtime;
                    
                    while(!stack.isEmpty()){
                        Homework remain = stack.pop();
                        
                        // 남는 시간 동안 멈춘 과제를 수행할 수 있는 경우
                        if(next.time >= CURR_TIME + remain.playtime){
                            answer.add(remain.name);
                            CURR_TIME += remain.playtime;
                        }
                        
                        // 남는 시간 동안 멈춘 과제를 다 수행할 수 없는 경우
                        else{
                            // 남은 시간만큼 수행 시간 감소 후 스택에 추가
                            remain.playtime -= next.time - CURR_TIME;
                            stack.add(remain);
                            break;
                        }
                    }
                    
                    
                }
                
                // 만약 현재 과제 끝내자마자 다음 과제 시작할 경우
                else if(next.time == CURR_TIME + curr.playtime){
                    answer.add(curr.name);
                    CURR_TIME += curr.playtime;
                    continue;
                }
                
                // 만약 다음 과제 시작 전까지 과제를 끝낼 수 없는 경우
                else{
                    // 남은 시간만큼 수행 시간 감소 후 스택에 추가
                    curr.playtime -= next.time - CURR_TIME;
                    stack.add(curr);
                }
                
            }
            
            // 남아있는 과제가 없다면
            else{
                // 현재 과제 수행
                answer.add(curr.name);
                
                // 멈춘 과제 수행
                if(!stack.isEmpty()){
                    while(!stack.isEmpty()){
                        answer.add(stack.pop().name);
                    }
                }
            }
            
        }
        
        return answer;
    }
    
    static int calTime(String time){
        String[] timeArr = time.split(":");
        int h = Integer.parseInt(timeArr[0]);
        int m = Integer.parseInt(timeArr[1]);
        return h*60 + m;
    }
    
    static class Homework implements Comparable<Homework>{
        String name;
        int time;
        int playtime;
        
        Homework(String name, int time, int playtime){
            this.name = name;
            this.time = time;
            this.playtime = playtime;
        }
        
        @Override
        public int compareTo(Homework o){
            return this.time - o.time;
        }
    }
}