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

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

평가

결과 : 성공
풀이시간 : 1시간 12분

너무 오래 풀었습니다.
리트코드 형태로 나오는 문제보다 프로그래머스 형태가 훨씬 까다롭다고 느껴집니다.
문제를 보고 아이디어를 떠올리는 것보다 구현하는 게 더 약하다는 생각이 들었습니다.
해당 문제도 풀이는 금방 생각했지만 코드 중간에 구멍이 있어, 디버깅을 하는데 오래걸렸습니다.

구현 위주의 연습을 해야겠다 판단이 듭니다.

아이디어

작업이 끝나는 순서대로 반환하는 문제입니다.
각 작업은 시작시간과 소요시간이 존재합니다.
만약에 작업을 하다가, 중간에 다른 작업이 시작하면 지금 하던 작업을 정지하고 새로 시작하는 작업을 수행합니다.(선점)

작업이 끝나면 잠깐 멈췄던 작업을 수행합니다. 이 때, 작업은 최근에 멈춘 순서대로 수행합니다.

이 문제를 보고 떠올린 건 두 가지입니다.
1. 멈춘 작업들은 스택에 저장을 해야겠다
2. 작업을 시작하는 순서대로 정렬하고 문제를 풀어야겠다

작업을 시작하면 이 작업을 끝낼 수 있는지 판단해야 합니다.
그러기 위해서 다음 작업의 시작시간과 비교합니다.
끝낼 수 있으면 작업을 끝내고 정답을 저장합니다.
끝낼 수 없으면 남아있는 작업량을 갱신하고 스택에 넣습니다.

수도코드

자세한 설명은 코드에 주석으로 설명을 첨부했습니다.

plan 빨리 시작하는 작업 순서로 정렬

for plan: plans:
  if now 끝나는시간 == next 시작시간:
    정답리스트.추가(now);
  else if now 끝나는 시간 < next 시작시간:
    정답리스트.추가(now);
    while(스택 순회):
      now 끝난 시간 = now.시작시간 + 작업시간
      now = 스택.pop();
      now.시작시간 = 갱신전 now 끝난 시간
      
      만약 stack에 들어간 작업을 끝낼 수 있으면
        정답리스트.추가(now);
      else (끝낼 수 없으면):
      	now.playtime을 줄여준다(작업한만큼)
        스택에 다시 추가
        마무리

스택에 남아있는 애들을 순서대로 정답리스트에 추가한다

return 정답리스트
  

정답 코드

import java.util.*;

class Solution {
    static int NAME = 0;
    static int START = 1;
    static int PLAYTIME = 2;
    
    // 중요: 모든 plan은 시작시간이 다르다!
    
    public String[] solution(String[][] plans) {
        String[] answer = new String[plans.length];
        
        // 빨리 시작하는 작업 순으로 정렬합니다.
        PriorityQueue<MyPlan> queue = new PriorityQueue<>((o1, o2) -> o1.start.value - o2.start.value);
        for(String[] plan: plans) {
            queue.add(new MyPlan(plan));
        }
        
        // 작업하다가 멈추면 Stack에 저장합니다.
        Stack<MyPlan> stack = new Stack<>();
        
        // 각 작업들을 확인합니다.
        int idx = 0;
        while(!queue.isEmpty()) {
            MyPlan now = queue.poll();
            
            // 마지막 작업이라면 정답리스트에 추가한다
            // 마지막 작업이면 작업을 뺏길 일 없이 끝까지진 행할 수 있습니다.
            if (queue.isEmpty()) {
                answer[idx++] = now.name;
                continue;
            }

			// 비교를 위해 다음 작업을 가져옵니다.
            MyPlan next = queue.peek();        

            // 작업을 끝낼 수 있는 상황입니다.
			// 12시에 시작하고 30분 걸리는 작업일 때, 다음 작업이 12시 40분인 그런 상황입니다.
            if (isNowEnd(now,next)) {
                // 지금 작업을 성공적으로 끝낸다
                answer[idx++] = now.name;
                            
                // 남은 시간동안 아직 덜끝낸 작업들을 한다
                while(!stack.isEmpty()) {
                	// 스택 가장 위에 있던 작업을 실행합니다.
                    // 해당 작업을 시작하는 시간은 갱신되기 전 now 작업이 끝난 시간입니다.
                    MyTime ending = new MyTime(now.start.value + now.playtime);
                    now = stack.pop();
                    now.start = ending;

                    // 스택에 있던 작업을 끝낼 수 있으면 끝냅니다.
                    if (isNowEnd(now, next)) {
                        answer[idx++] = now.name;
                    } else { 
                        // 다음 작업이 시작하기 전까지, 작업을 끝내지 못하는 상황입니다.
						// 할 수 있는 만큼 일하고 stack에 남은 작업을 넣습니다.
                        now.playtime -= (next.start.value - now.start.value);
                        stack.push(now);
                        
                        // 스택에 있는 작업들을 더 이상 수행할 수 없으므로 break로 탈출합니다.
                        break;
                    }
                }
            } else { // 지금 작업을 끝낼 수 없는 상황입니다.
				// 할수 있는 만큼 일하고 stack에 남은 작업을 넣습니다.
                int workingTime = next.start.value - now.start.value;
                now.playtime -= workingTime;
                stack.add(now);
            }
        }
        
        // 스택에 있는거 다 추가한다
        while(!stack.isEmpty()) {
            MyPlan plan = stack.pop();
            answer[idx++] = plan.name;
        }
        return answer;
    }
        
    public boolean isSame(MyPlan now, MyPlan next) {
        return now.start.value + now.playtime == next.start.value;
    }
    public boolean isNowEnd(MyPlan now, MyPlan next) {
        return now.start.value + now.playtime <= next.start.value;
    }            
    
    static class MyPlan {
        String name;
        MyTime start;
        int playtime;
        
        public MyPlan(String[] args) {
            this.name = args[0];
            this.start = new MyTime(args[1]);
            this.playtime = Integer.parseInt(args[2]);
        }
    }
    
    static class MyTime {
        int value;
        
        public MyTime(String time) {
            String[] temps = time.split(":");
            int hour = Integer.parseInt(temps[0]);
            int minute = Integer.parseInt(temps[1]);
            
            this.value = hour * 60 + minute;
        }
        
        public MyTime(int value) {
            this.value = value;
        }
        
        public boolean equals(MyTime obj) {
            return this.value == obj.value;
        }
    }
}