[Programmers / Level 2] 176962. 과제 진행하기 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/176962
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/과제 진행하기

입출력 조건

입출력 예시

문제 이해

• 과제를 스케줄링하여 끝낸 순으로 배열로 출력하면 되는 문제

알고리즘

풀이 시간 : 45분

• 입력

  • 과제 시작 시간 : 분 단위 정수로 변환
  • plans 배열 -> 시작 시간 기준으로 오름차순 정렬

• 스택

  • 진행 중인 과제를 멈추면 스택에 저장(후입선출)
  • 새로운 과제 시작 -> 현재 과제를 멈추고 스택에 push

• 과제 처리

  • 다음 과제 시작 전 남은 시간 : gap
  • gap 동안 스택 과제(=가장 최근에 멈춘 것)를 이어서 진행
  • gap > 과제 소요 시간 : 해당 과제 완료 후 answer에 추가, gap 감소
  • gap < 과제 소요 시간 : 남은 소요 시간만큼만 진행 -> 다시 스택에 push

• 반환

  • 스택에 남은 과제들을 최근에 멈춘 순서대로 answer에 추가

import java.util.*;

class Solution {
    static class Task {
        String name;
        int start;
        int duration;

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

    public String[] solution(String[][] plans) {
        int n = plans.length;
        List<Task> tasks = new ArrayList<>();
        for (String[] plan : plans) {
            String name = plan[0];
            String[] time = plan[1].split(":");
            int start = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
            int duration = Integer.parseInt(plan[2]);
            tasks.add(new Task(name, start, duration));
        }

        tasks.sort(Comparator.comparingInt(t -> t.start));

        Stack<Task> stack = new Stack<>();
        List<String> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            Task curr = tasks.get(i);
            int nextStart = (i < n - 1) ? tasks.get(i + 1).start : Integer.MAX_VALUE;
            stack.push(new Task(curr.name, curr.start, curr.duration));
            int gap = nextStart - (curr.start);

            while (!stack.isEmpty() && gap > 0) {
                Task top = stack.pop();
                if (top.duration <= gap) {
                    answer.add(top.name);
                    gap -= top.duration;
                } else {
                    top.duration -= gap;
                    stack.push(top);
                    break;
                }
            }
        }

        while (!stack.isEmpty()) {
            answer.add(stack.pop().name);
        }

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

결과

✍️ 다른 풀이 - 우선순위 큐

• 시작 시간 기준으로 우선순위 큐에 저장
• 현재 시간, 다음 과제 시작 시간을 비교하는 방식 사용
• 멈춘 과제 : 다른 큐(리스트)에 저장 -> 새 과제가 없을 때 이어서 처리하는 방식!

import java.util.*;

class Solution {
    static class Task implements Comparable<Task> {
        String name;
        int start;
        int duration;
        Task(String name, int start, int duration) {
            this.name = name;
            this.start = start;
            this.duration = duration;
        }
        @Override
        public int compareTo(Task o) {
            return this.start - o.start;
        }
    }

    public String[] solution(String[][] plans) {
        PriorityQueue<Task> pq = new PriorityQueue<>();
        for (String[] plan : plans) {
            String[] time = plan[1].split(":");
            int start = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
            pq.add(new Task(plan[0], start, Integer.parseInt(plan[2])));
        }

        List<String> answer = new ArrayList<>();
        List<Task> paused = new ArrayList<>();
        int now = 0;

        while (!pq.isEmpty()) {
            Task curr = pq.poll();
            now = Math.max(now, curr.start);

            // 다음 과제 시작 전까지 현재 과제 끝낼 수 있는지 확인
            int nextStart = pq.isEmpty() ? Integer.MAX_VALUE : pq.peek().start;
            if (now + curr.duration <= nextStart) {
                now += curr.duration;
                answer.add(curr.name);

                // 남은 시간 동안 멈춘 과제 이어서 처리
                while (!paused.isEmpty() && now < nextStart) {
                    Task last = paused.remove(paused.size() - 1);
                    if (now + last.duration <= nextStart) {
                        now += last.duration;
                        answer.add(last.name);
                    } else {
                        last.duration -= (nextStart - now);
                        paused.add(last);
                        now = nextStart;
                        break;
                    }
                }
            } else {
                // 끝내지 못하면 남은 시간만큼만 진행하고 멈추기
                curr.duration -= (nextStart - now);
                paused.add(curr);
                now = nextStart;
            }
        }

        // 멈춘 과제 이어서 처리
        for (int i = paused.size() - 1; i >= 0; i--) {
            answer.add(paused.get(i).name);
        }

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