[ Programmers - LV2 ] 과제 진행하기

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

프로그래머스

 

단순 구현 문제로 자료구조를 사용하기 나름인 문제인 것 같았는데, 애좀 먹었다.

다른 사람들 풀이를 보니까 다양한 풀이가 있었는데 나는 자바에서 제공하는 LocalDateTime 클래스를 이용해서 시간들을 제어하려고 시도 했다.

 

처음에는 LocalTime 이면 해결 될 줄 알았는데, 23:59 에서 시간이 오버 플로우(?) 되면 대응이 안되기 때문에 중간 과정에서 변경이 불가피했다.

---

📌 분석

/**
 * 1. 새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작 합니다.
 * 2. 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행 합니다.
 * 3. 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
 * 4. 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
 */

 

구현 문제에서 집중해야하는 부분은 주어진 조건을 그대로 적용하는 것이다.

그래서 나는 조건을 항상 문제 풀 때에는 위에다 적어두고, 리마인드 할 수 있도록 한다.

 

특별한 분석은 필요 없이 문제를 잘 읽는게 중요한 점이다.

1. Input 볼륨 확인하기
2. String 값들이 주어지기 때문에 어떻게 내가 필요한 값으로 파싱 할 것인가
3. 조건 확인

---

📌 풀이

[ 그림으로 보는 자료구조 세팅 ]

• tasks(PriorityQueue): 과제들의 시작 시간 기준으로 정렬된 우선순위 큐
• pendingTask(Stack): 임시 중지되는 과제들을 보관하는 자료구조
• curTask(Task): 현재 수행중인 과제 (소요 시간, 과제 이름, 시작 & 종료 시간)

[ 초기 상태 ]

문제에서 주어지는 예시를 기준으로 설명할 때 처음에는 tasks 에 시작 시간 순서대로 정렬되어 있다.

[ 과제 진행 시작 ]

가장 빠르게 시작할 수 있는 music 이 수행된다.

 

[ music 과제가 임시 중지 ]

12:20 분에 시작한 music 과제는 소요 시간이 40분인데 12:30 분에 시작하는 computer 과제가 있기 때문에 10분만 수행되고 임시 중지 된다.

 

위 그림과 같은 플로우로 computer 과제도 science 과제에 밀려서 10분 수행되고 임시 중지 되게 된다.

[ 가장 먼저 끝나는 과제 ]

science 과제는 12:40 에 시작하고, 소요 시간이 50분 이기 때문에 예상 종료 시간은 13:30 분이고, 대기중인 history 과제는 시작 시간이 14:00 이기 때문에 끝까지 수행될 수 있다.

 

science 과제가 종료되면 13:30 인데, 14:00 까지 30분의 시간이 남기 때문에 임시 중지 되었던 computer 과제를 30분 수행하고 난 뒤 14:00 에 history 과제가 시작된다.

 

history 뒤에 남은 과제는 없기 때문에 끝까지 수행될 수 있다.

[ 임시 중지 되었던 과제들 일괄 마무리 ]

남은 과제는 시작 & 종료 시간과 소요 시간을 고려할 필요 없이 가장 최근에 중지 되었던 과제 순서로 수행하면 된다.

---

📌 고려상황

내 풀이는 처음에 1 ~ 10 번 케이스가 차례로 다 틀려서 당황 했었는데, 위 그림에서는 computer 과제가 현재 시간과 다음 과제 시작 시간과의 여유가 있어서 중간에 30분 수행 되었는데, 나는 처음에 이 상황을 고려하지 않았었다.

[ 고려 사항 예시 ]

Task1, 2, 3 은 다 과제를 다 끝내지 못하고 중지되었다고 가정하고, Task4 가 끝나는 시점에서 시간은 시작(12:30), 소요(30) 이니까 종료 시간(13:00) 이다.

 

다음 과제 Task6 까지의 시간이 1시간 남아있기 때문에 그 여유 시간동안 Task3, 2 를 끝낼 수 있다.

[ Task3, 2 종료 ]

 

Task3, 2 를 끝내고, Task1 수행 중에는 14:00 에 도달해서 20분 수행 후 Task6 이 실행된다.

[ 모든 과제 종료 ]

과제의 종료 순서는 (지금 보니까 Task5 는 없다...) 아래와 같게 되겠다.

Task4 -> Task3 -> Task2 -> Task6 -> Task1

---

📌 코드 - Java

풀이가 간단하면 주석 없이도 풀지만.... 이런 문제는 주석이 없으면 나도 헷갈린다.

풀이하면서 제일 불편했던 점은 stack 과 queue 에 요소가 들어 있는지 isEmpty() 를 계속 확인해주는 조건을 넣어줘야 했다는점?

import java.time.Duration;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.LocalTime;
import java.util.*;

public class LV2_176962 {
    /**
     * 1. 새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작 합니다.
     * 2. 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행 합니다.
     * 3. 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
     * 4. 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
     */
    static class Solution {
        public String[] solution(String[][] plans) {
            Queue<Task> tasks = new PriorityQueue<>((a, b) -> a.srtTime.isAfter(b.srtTime) ? 1 : -1);
            Stack<Task> pendingTasks = new Stack<>();
            List<Task> taskEndSeq = new ArrayList<>();

            for(String[] plan : plans) {
                tasks.add(new Task(plan));
            }

            LocalDateTime curTime;

            while(!tasks.isEmpty()) {
                Task curTask = tasks.poll();

                // 다음 과제가 있음 && 현재 과제가 진행중에 새로운 과제할 시간이됨
                if(!tasks.isEmpty() && tasks.peek().srtTime.isBefore(curTask.endTime)) {
                    Task nextTask = tasks.peek();
                    long timeGap = curTask.getTimeGap(nextTask);

                    curTask.spendTime -= timeGap;  // 과제 진행 시간 감소
                    pendingTasks.push(curTask);  // 뒤로 미루기
                    continue;
                }

                curTime = curTask.endTime;  // 현 과제 종료 하면서 끝나는 시간 기록
                taskEndSeq.add(curTask);  // 과제 종료

                // 임시 중지 과제 있음 && 다음 과제 있음 && 현재 시간이랑 다음 과제 시간 사이 차이가 있음
                if(!pendingTasks.isEmpty() && !tasks.isEmpty() && curTime.isBefore(tasks.peek().srtTime)) {
                    Task nextTask = tasks.peek();
                    Task pendingTask = pendingTasks.peek();
                    long timeGap = Duration.between(curTime, nextTask.srtTime).toMinutes();  // 현재 시간과 다음 시작 과제의 시간차이

                    while(timeGap >= 0) {  // 다음 시작 과제 시간전 여유 시간이 있을 때
                        if(pendingTask.spendTime <= timeGap) {  // 여유 시간으로 과제를 끝낼 수 있을 때
                            timeGap -= pendingTask.spendTime;  // 사용한 여유 시간 감소
                            curTime = pendingTasks.peek().endTime;  // 현재 시간 갱신
                            taskEndSeq.add(pendingTasks.pop());

                            if(pendingTasks.isEmpty()) break;

                            pendingTask = pendingTasks.peek();
                        } else {  // 여유 시간으로 끝낼 수 없을 때 시간만 감소
                            pendingTask.spendTime -= timeGap;
                            break;
                        }
                    }
                }
            }

            while(!pendingTasks.isEmpty()) {
                taskEndSeq.add(pendingTasks.pop());
            }

            return taskEndSeq.stream().map(Task::getSubject).toArray(String[]::new);
        }
    }

    static class Task {
        final String subject;
        LocalDateTime srtTime;
        LocalDateTime endTime;
        int spendTime;

        public Task(String[] info) {
            this.subject = info[0];
            this.spendTime = Integer.parseInt(info[2]);

            Integer[] time = Arrays.stream(info[1].split(":")).map(Integer::parseInt).toArray(Integer[]::new);

            this.srtTime = LocalDateTime.of(LocalDate.now(), LocalTime.of(time[0], time[1]));
            this.endTime = this.srtTime.plusMinutes(this.spendTime);
        }

        public String getSubject() {
            return subject;
        }

        public long getTimeGap(Task task) {
            return Duration.between(this.srtTime, task.srtTime).toMinutes();  // (현)과제와 (새)과제 시간차
        }
    }
}

---

📌 결과

[ 결과 - Java ]

---

📌  오늘처럼 정리한 이유는?

문제의 풀이를 하기 전에 생각난 아이디어가 있었고, '이렇게 풀어도 되나' 라는 생각을 가지고 접근했었기 때문에 온전히 나의 생각만 들어갔기 때문이다.

 

시간은 조금 걸렸고, 내가 주로 문제 풀 때 머릿속에 그리는 자료구조 아키텍처를 표현할 수 있는 시간이 될 것 같아서 그림과 같이 풀이