프로그래머스 - 과제 진행하기(java)

📓문제

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

📓풀이

과제가 끝날 시간과 다음과제가 시작될 시간의 차인 remainTime 이 핵심값

remainTime == 0
과제가 끝남과 동시에 다음 과제 시작

remainTime < 0
과제를 다 못했는데 다음 과제가 시작됨
과제를 미뤄야함

remainTime > 0
과제를 다 했는데 다음 과제까지 시간이 남음
미뤄둔 과제가 있다면 할 수 있음

• 과제를 둘로 나누어 생각한다.
  계획된 과제와 미뤄둔 과제

• 계획된 시간에 맞춰 과제를 진행한다.
  위 처럼 remainTime을 계산하여 시간이 맞지 않으면 과제를 미루거나 밀린 과제를 한다.

• 마지막 시간에 시작하는 과제는 중간에 그만둬야하는 경우가 없다.
  → 다음 과제 시작시간을 예상종료시간(start + play)과 똑같이 정하면 된다.

• 마지막 과제가 끝나면 미뤄둔 과제들은 play 시간과 상관 없이 차례로 끝내면된다.

📓코드

public List<String> solution(String[][] plans) {
   List<String> answer = new ArrayList<>();

   PriorityQueue<Integer> startQ = new PriorityQueue<>();
   Map<Integer, String> startNameMap = new HashMap<>();
   Map<String, Integer> namePlayMap = new HashMap<>();

   for(String[] plan : plans){
       String name = plan[0];
       int start = Integer.parseInt(plan[1].substring(3,5)) + (Integer.parseInt(plan[1].substring(0,2)) * 60);
       int playTime = Integer.parseInt(plan[2]);
       startQ.add(start);
       startNameMap.put(start, name);
       namePlayMap.put(name, playTime);
   }        
   
   Stack<String> postponedTask = new Stack<>();
   //1. 주어진 시간대로 과제하기
   while(!startQ.isEmpty()){
       int now = startQ.poll();
       String name = startNameMap.get(now);        //해야할 과제명
       int endTime = now + namePlayMap.get(name);  //예상 종료시간
       int nextStartTime = (!startQ.isEmpty()) ? startQ.peek() : endTime;// 다음 과제 시작 시간
       //1-1. 시간 계산
       int remainTime = nextStartTime - endTime;

       //1-2. A. 과제를 다했다
       if(remainTime >= 0){
           answer.add(name);//A-1. 완료처리
           while (remainTime > 0){//A-2. 남은 시간 활용하기
               if(!postponedTask.isEmpty()){//A-3. 미뤄둔 과제가 있다.
                   String postponed = postponedTask.peek();
                   int postponedTime = namePlayMap.get(postponed);
                   if (postponedTime <= remainTime){//A-3. 남은 시간동안 완료함(완료처리)
                       answer.add(postponedTask.pop());
                   }else{//A-3. 남은 시간동안 다 못함
                       namePlayMap.put(postponed, postponedTime - remainTime);
                   }
                   remainTime -= postponedTime;
               }else break;
           }
       }
       //1-2. B. 과제를 다 못함..
       else{
           namePlayMap.put(name, Math.abs(remainTime));
           postponedTask.push(name);//B-1. 과제 미루기
       }
   }
   //2. 미뤄둔 과제 차례로 완료하기
   while(!postponedTask.isEmpty()){
       answer.add(postponedTask.pop());
   }
   return answer;
}