[코테]프로그래머스 - 과제 진행하기

문제

문제 설명

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.
과제는 시작하기로 한 시각이 되면 시작합니다.
새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

제한사항

제한사항
3 ≤ plans의 길이 ≤ 1,000
plans의 원소는 [name, start, playtime]의 구조로 이루어져 있습니다.
name : 과제의 이름을 의미합니다.
2 ≤ name의 길이 ≤ 10
name은 알파벳 소문자로만 이루어져 있습니다.
name이 중복되는 원소는 없습니다.
start : 과제의 시작 시각을 나타냅니다.
"hh:mm"의 형태로 "00:00" ~ "23:59" 사이의 시간값만 들어가 있습니다.
모든 과제의 시작 시각은 달라서 겹칠 일이 없습니다.
과제는 "00:00" ... "23:59" 순으로 시작하면 됩니다. 즉, 시와 분의 값이 작을수록 더 빨리 시작한 과제입니다.
playtime : 과제를 마치는데 걸리는 시간을 의미하며, 단위는 분입니다.
1 ≤ playtime ≤ 100
playtime은 0으로 시작하지 않습니다.
배열은 시간순으로 정렬되어 있지 않을 수 있습니다.
진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단합니다.

입출력 예

문제 요약

• 복수개의 과제를 가진 배열이 매개변수로 주어짐.
• 과제는 이름, 시작시간, 수행시간을 순서대로 가지는 1차원 배열임.
• 과제는 시작시간이 되면 시작함.
• 새로운 과제를 해야하는 시간에 이미 수행중인 과제가 있다면 새로운 과제를 먼저 수행함.
• 중단된 과제는 멈춘 시점까지의 수행한 시간을 계산해야함.
• 현재 진행중인 과제가 종료되고 새로운 과제까지의 남은 시간을 계산해서 시간이 남는다면 중단된 과제를 수행함.
• 하지만 새로운 과제까지 시작하기까지 시간이 남지 않는다면 새로운 과제를 우선적으로 수행함.
• 여기서 현재 과제의 종료시간과 새로운 과제의 시작시간이 같다면 현재 과제는 종료한 것으로 함.
• 이런 부분들을 고려하여 과제가 종료되는 순서대로 이름을 반환해야함.

문제 분석

이번 문제는 기존에 풀던 코딜리티의 문제보다 수준이 높았음. 나는 다음과 같이 문제를 분석했다.

• 각 과제의 시작 시간을 기준으로 정렬을 수행하여 시작 순서가 빠른 순으로 진행되도록 준비했다.
• 우선적으로 수행할 것은 이전에 저장된 과제와 현재 수행될 과제의 종료시간과 시작시간을 비교한다.
• 시간이 작거나 같다면 종료한 것으로 판단하고, 과제의 이름을 정답 배열에 추가한다.
• 수행될 과제의 시작시간이 더 크다면 현재 과제를 Stack에 저장하고 다음과제를 수행한다.
• 반복하면서 현재 과제와 수행될 과제의 시간에서 텀이 발생하면 멈춘 과제의 가장 최신을 불러와 수행한다.
• 또 다시 새로운 과제를 수행할 시간이 되면 현재 과제는 stack에 저장하고 위의 과정을 반복한다.

여기서 배열의 길이가 1,000이하 이기 때문에 시간복잡도를 크게 고려하지 않았다. 다만, Stack을 이용해 가장 최근에 멈춘과제를 빼와서 비교하는 방법에 초점을 두고 작성을 하였다.

실패 코드

다음은 내가 최초 계획한 부분에서 실패한 코드이다.

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 과제진행하기 {
	
    // 과제 객체
    public static class Plan {
        String name;
        int time;
        int playTime;

        public Plan(String name, int time, int playTime) {
            this.name = name;
            this.time = time;
            this.playTime = playTime;
        }
    }

    public static String[] solution(String[][] plans) {
        String[] answer = new String[plans.length];
        List<Plan> list = new ArrayList<>();
        Stack<Plan> stack = new Stack<>();

        // 시각을 숫자로 변환
        for (int i = 0; i < plans.length; i++) {
            String name = plans[i][0];
            int hour = 60 * Integer.valueOf(plans[i][1].split(":")[0]);
            int time = hour + Integer.valueOf(plans[i][1].split(":")[1]);
            int playTime = Integer.valueOf(plans[i][2]);

            list.add(new Plan(name, time, playTime));
        }
        // 시각을 기준으로 정렬
        list.sort((o1, o2) -> {
            return o1.time - o2.time;
        });

        for (int i = 0; i < list.size(); i++) {
        	// 반복문의 마지막에는 stack에 남은 과제가 있는지만 비교
            if (i == list.size() - 1) {
                answer[i] = stack.size() > 0 ? stack.pop().name : list.get(i).name;
            } else {
                Plan prePlan = list.get(i);
                Plan curPlan = list.get(i + 1);

                int sum = prePlan.time + prePlan.playTime;

                if (sum <= curPlan.time) {
                    answer[i] = prePlan.name;
                    // 이 부분에서 정확히 해결되지 않았다.
                    if (stack.size() > 0) {
                        Plan stopPlan = stack.pop();
                        if (curPlan.time - sum > stopPlan.playTime) answer[i] = stopPlan.name;
                        else stack.push(stopPlan);
                    }
                } else {
                    prePlan.playTime = curPlan.time - sum;
                    stack.push(prePlan);
                }
            }
            System.out.println(answer[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        String[][] plans = {{"korean", "11:40", "30"}, {"english", "12:10", "20"}, {"math", "12:30", "40"}};

        System.out.println(solution(plans));
    }
}

위 과정을 수행하면서 1시간 정도를 풀었지만 해답이 나오지 않아 다른 사람들의 풀이를 참고하였는데, PriorityQueue과 Stack을 사용한 사람도 있었고, 다양한 풀이가 많았지만 나는 재귀함수와 Stack을 이용해서 풀어나간 분의 코드를 분석하고 다음에 사용해보기로 했다.

풀이 코드

package test.level2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

public class 과제진행하기2 {

    public static class Task {
        String name;
        int startTime;
        int playTime;

        public Task(String name, String startTime, String playTime) {
            this.name = name;
            this.startTime = timeToMinute(startTime);
            this.playTime = Integer.valueOf(playTime);
        }

        // String -> Integer 시간으로 변경
        public int timeToMinute(String start) {
            String[] arr = start.split(":");
            int h = Integer.valueOf(arr[0]) * 60;
            int m = Integer.valueOf(arr[1]);

            return h + m;
        }
    }

    // 재귀적으로 Stack에서 비교
    public static void recursivePop(Stack<Task> stack, Task newTask, int curTime, List<String> answer) {
        if (stack.isEmpty()) return;

        // 진행 중인 과제
        Task curTask = stack.peek();
        if (curTime + curTask.playTime <= newTask.startTime){
            answer.add(stack.pop().name);
            // 진행중인 과제가 새로운 과제의 시작시간보다 작거나 같다면
            // 재귀함수 호출
            recursivePop(stack, newTask, curTime + curTask.playTime, answer);
        } else {
            curTask.playTime -= newTask.startTime - curTime;
        }
    }

    public static String[] solution(String[][] plans) {
        // 과제 배열 List로 변환
        List<Task> taskList = Arrays.stream(plans)
                .map(plan -> new Task(plan[0], plan[1], plan[2]))
                .collect(Collectors.toList());

        // 오름차순 정렬
        taskList.sort((o1, o2) -> {
            return o1.startTime - o2.startTime;
        });

        // 진행중인 과제를 저장
        Stack<Task> stack = new Stack<>();
        List<String> answer = new ArrayList<>();

        // 현재 시간 초기화
        int curTime = -1;

        for (int i = 0; i < taskList.size(); i++) {
            // 진행중인 과제가 없다면 과제 삽입
            if (stack.isEmpty()) {
                stack.push(taskList.get(i));
                continue;
            }

            // 진행중인 과제와 새로운 과제가 있는 경우
            Task curTask = stack.peek();
            Task newTask = taskList.get(i);

            // 새로운 과제의 시작시간과 진행중 과제의 종료시간을 비교하기 위해 세팅
            curTime = curTask.startTime;

            if (curTime + curTask.playTime <= newTask.startTime) {
                // 재귀함수 호출
                recursivePop(stack, newTask, curTime, answer);
            } else {
                // 현재 수행중인 과제를 중단하고 시간 갱신 및 새 과제 수행
                // 새로운 과제의 시작시간과 현재 수행과제의 시작시간의 차이를 수행시간에서 빼기
                curTask.playTime -= newTask.startTime - curTime;
            }

            stack.push(newTask);
        }

        // 과제에 대한 반복문 종료 후
        // 남아있는 stack의 이름을 순서대로 저장
        while (!stack.isEmpty()) {
            answer.add(stack.pop().name);
        }

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

    public static void main(String[] args) {
        String[][] plans = {{"korean", "11:40", "30"}, {"english", "12:10", "20"}, {"math", "12:30", "40"}};

        System.out.println(solution(plans));
    }
}

나와 비교했을 때 나는 문제에서 현재 중단된 과제만 Stack에 저장을 했다가 다음 수행될 과제와 비교하는 형태로 진행하였는데, 풀이는 모든 과제를 Stack에 저장하는 방식으로 진행하고 그때 그때 꺼내서 저장 후 남아있는 과제는 순서대로 최종적으로 결과에 반영하는 모습을 보여주었다.

여기서 내가 아직 부족한 부분은 재귀함수를 사용하는 방법이라고 생각한다. 전체적인 큰 틀에서 흐름은 유사했다는 것을 느꼈지만 보다 효율적인 비교를 할 수 있었던 것은 재귀함수의 활용이라는 생각을 하게되었다. 이런 부분들을 계속 코딩 테스트를 수행하면서 습득해야겠다는 생각을 했다.