[pro] 프로그래머스 level2 176962 과제 진행하기 (Java) - 그리디

[문제]

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

프로그래머스

 

[풀이]

1. 과제 시작 시간 기준 오름차순 정렬해서 우선순위 큐에 넣어둔다.

2. 새로운 과제가 있다면 그 과제를 시작한다. 만약 현재시각+새로운 과제 소요 시간이 그 다음 과제 시작 시간보다 더 오래걸린다면 중간에 과제를 멈춰야 한다. 따라서 과제를 수행한 시간을 뺀 다음, stack에 멈춘 과제를 넣고, 새로운 과제를 시작한다. 현재 시간도 갱신해준다.

멈춘 과제를 다시 할 때, 가장 최근에 멈춘 과제부터 수행해야 하기 때문에  stack을 이용해 저장해주었다.

3. 만약 과제를 멈추지 않고 끝낼 수 있다면, 정답 배열에 그 과제 이름을 저장해주고 현재 시간을 갱신한다.

- 현재 시각에 시작할 수 있는 새로운 과제가 있다면 그 과제를 시작한다.

- 현재 시각에 새로 시작할 수 있는 과제가 없고, 멈춰둔 과제가 있다면 가장 최근에 멈춘 과제를 다시 시작한다.

- 멈춰둔 과제가 없고, 일정 시간 후에 시작해야 할 과제가 있다면 그 과제를 시작한다. 이때 현재 시각을 갱신해야 함에 주의!

- 위의 경우가 다 아니라면 break문을 통해 반복문을 빠져나온다.

 

[코드]

 

import java.util.*;

class Solution {
    class Subject implements Comparable<Subject>{
        String name;
        int start, playtime;
        Subject(String name, int start, int playtime){
            this.name = name;
            this.start = start;
            this.playtime = playtime;
        }
        
        @Override
        public int compareTo(Subject s){
            return this.start - s.start; //시작시간 오름차순 정렬
        }
    }
    
    
    public String[] solution(String[][] plans) {
        String[] answer = {};
        //과제를 끝낸 순서대로 이름을 배열에 담아 return
        //새로 시작한 과제 -> 중간에 멈춘 과제
        
        answer = new String[plans.length];
        int idx = 0;
        PriorityQueue<Subject> q = new PriorityQueue<>((o1, o2)->(o1.start-o2.start));
        for(String[] p:plans){
            q.add(new Subject(p[0], convertTime(p[1]), Integer.parseInt(p[2])));
        }

        Subject s = q.poll();
        int now = s.start;
        
        Stack<Subject> stack = new Stack<>(); //멈춘 과제들
        while(true){
            if(!q.isEmpty() && now+s.playtime > q.peek().start){
                //과제 중지
                stack.push(new Subject(s.name, s.start, s.playtime-(q.peek().start-now)));
                
                now = q.peek().start;
                
                s = q.poll(); //새로운 과제 시작
            }
            else{
                //과제 끝냄
                answer[idx++] = s.name;
                now += s.playtime;
                
                //새로 시작해야 하는 과제가 있다면 새로운 과제 시작
                if(!q.isEmpty() && now==q.peek().start){
                    s = q.poll();
                }
                else if(!stack.isEmpty()){
                    //멈춰둔 과제 다시 시작
                    s = stack.pop();
                }
                else if(!q.isEmpty()){
                    s = q.poll();
                    now = s.start;
                }
                else break;
            }
        }
        
        return answer;
    }
    
    public static int convertTime(String t){
        String[] str = t.split(":");
        int min = Integer.parseInt(str[0])*60 + Integer.parseInt(str[1]);
        return min;
    }
}