[programmers] 과제 진행하기

15 Apr 2023 in Algorithm on Algorithm

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

import java.util.*;

class Solution {
    public String[] solution(String[][] plans) {
        List<String> answer = new ArrayList<>();
        Stack<Plan> stack = new Stack<>();

        // 시작 시간 기준 정렬
        Arrays.sort(plans, Comparator.comparingInt(p -> toMinutes(p[1])));

        for (int i = 0; i < plans.length; i++) {
            String name = plans[i][0];
            int startTime = toMinutes(plans[i][1]);
            int duration = Integer.parseInt(plans[i][2]);

            // 다음 과제 전까지의 여유 시간
            if (i < plans.length - 1) {
                int nextStartTime = toMinutes(plans[i + 1][1]);
                int availableTime = nextStartTime - startTime;

                if (availableTime >= duration) {
                    // 과제 끝내기
                    answer.add(name);
                    availableTime -= duration;

                    // 스택에서 멈춘 과제 이어서 처리
                    while (!stack.isEmpty() && availableTime > 0) {
                        Plan paused = stack.pop();
                        if (availableTime >= paused.duration) {
                            answer.add(paused.name);
                            availableTime -= paused.duration;
                        } else {
                            paused.duration -= availableTime;
                            stack.push(paused);
                            break;
                        }
                    }
                } else {
                    // 시간이 부족하면 과제 중단하고 스택에 저장
                    stack.push(new Plan(name, duration - availableTime));
                }
            } else {
                // 마지막 과제는 무조건 끝내기
                answer.add(name);
            }
        }

        // 남은 중단 과제 처리
        while (!stack.isEmpty()) {
            answer.add(stack.pop().name);
        }

        return answer.toArray(new String[0]);
    }

    private int toMinutes(String time) {
        String[] split = time.split(":");
        return Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
    }

    private static class Plan {
        String name;
        int duration;

        Plan(String name, int duration) {
            this.name = name;
            this.duration = duration;
        }
    }
}