176962. 과제 진행하기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/176962

제한사항

풀이

import java.util.*;

class Solution {
    class Task {
        private String name; 
        private Integer startTime;
        private Integer playTime;
        
        public Task(String name, Integer startTime, Integer playTime) {
            this.name = name;
            this.startTime = startTime;
            this.playTime = playTime;
        }
        
        public Task(String name, Integer playTime) {
            this.name = name;
            this.playTime = playTime;
        }
    }
    public List<String> solution(String[][] plans) {
        List<String> answer = new ArrayList<>();
        PriorityQueue<Task> pq = new PriorityQueue<>((o1, o2) -> o1.startTime - o2.startTime);
        Stack<Task> remainTasks = new Stack<>();
        
        for(String[] plan : plans) {
            String name = plan[0];
            String[] t = plan[1].split(":");
            Integer startTime = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
            Integer playTime = Integer.parseInt(plan[2]);
            pq.add(new Task(name, startTime, playTime));
        }
        
        while(!pq.isEmpty()) {
            Task curTask = pq.poll();
            
            Integer curTime = curTask.startTime;
            
            if(!pq.isEmpty()) {
                Task nextTask = pq.peek();
                
                // 다음 과제 시작 시간과 진행 시간이 겹칠 경우
                if(curTask.startTime + curTask.playTime > nextTask.startTime) {
                    Integer remainTime = curTask.startTime + curTask.playTime - nextTask.startTime;
                    remainTasks.push(new Task(curTask.name, remainTime));
                    
                }
                // 다음 과제 시작 시간과 종료 시간이 일치할 경우
                else if(curTask.startTime + curTask.playTime == nextTask.startTime)  {
                    answer.add(curTask.name);
                    
                } 
                // 다음 과제 시작 전까지 시간이 남을 경우
                else {
                    curTime += curTask.playTime;
                    answer.add(curTask.name);
                    
                    // 잠시 멈춘 과제를 수행
                    while(!remainTasks.isEmpty()) {
                        Task remainTask = remainTasks.pop();
                        
                        if(curTime + remainTask.playTime <= nextTask.startTime) {
                            answer.add(remainTask.name);
                            curTime+=remainTask.playTime;
                            continue;
                        } else {
                            Integer t = curTime + remainTask.playTime - nextTask.startTime;
                            remainTasks.push(new Task(remainTask.name, t));
                            break;
                        }
                    }
                    
                }
                
            }
            // 다음 과제가 없고 현재 과제가 마지막일 경우
            else {
                // 현재 과제를 끝내고 잠심 멈춘 과제를 끝낸다.
                answer.add(curTask.name);
                curTime+=curTask.playTime;
                
                while(!remainTasks.isEmpty()) {
                    Task task = remainTasks.pop();
                    answer.add(task.name);
                    curTime+=task.playTime;
                        
                }
            }
        }
        return answer;
    }
}

회고

과제는 시간 순으로 진행하고, 진행 중에 새 과제 시작 시간과 겹치면 진행 중이던 과제는 잠시 멈추고 새 과제를 시작한다. 잠시 멈춘 과제는 새 과제가 없거나 새 과제 시작 시간 사이에 남는 시간이 있으면 진행한다. 멈춘 과제를 수행할 때는 마지막으로 멈춘 과제를 먼저 수행한다.

 

과제를 시간 순으로 수행하기 때문에 우선순위로 큐에 과제 정보를 넣어서 정렬시켰다. 잠시 멈춘 과제를 시작할 때는 최신 과제를 먼저 수행해야 되기 때문에 잠시 멈춘 과제는 스택에 보관하도록 했다.

 

현재 과제와 다음 과제를 비교해야하기 때문에 큐에서 먼저 과제를 꺼내고 다음 과제가 있으면(큐가 비어있지 않으면) 다음 과제를 꺼내서 비교를 수행했다.

• 다음 과제 시작 시간과 현재 과제 진행 시간이 겹치면 현재 진행 과제를 멈추고 남은 진행 시간을 계산해서 스택에 보관한다.
• 다음 과제 시작 시간과 현재 과제 종료 시간과 동일하면 answer에 추가하고 다음 과제를 진행한다. 스택에 넣을 과제는 없다.
• 다음 과제 시작 시간과 현재 과제 종료 시간이 겹치지지 않으면 answer에 현재 끝낸 과제를 추가하고 잠시 멈춘 과제(스택)들을 처리한다.

 

잠시 멈춘 과제(스택) 처리

• 잠시 멈춘 과제의 종료시간과 다음 과제 시작 시간을 비교한다.
• 겹치면 남은 시간을 계산해서 스택에 넣고 다음 과제를 진행한다.
• 겹치지 않으면 계속해서 다음 멈춘 과제(stack.pop) 진행한다.