[Java/Stack] 프로그래머스. 과제 진행하기

🤔 Intuition

새 과제가 오면 stash 해두고 나중에 시간 남을떄마다 꺼내보는 구조이므로 stack 문제겠다.

정답률이 낮아서 조금 쫄았지만, 별거 없는 문제였다. 백준에서 유사한 문제를 풀어봤었기에 접근이 어렵지 않았다.

🔎 Algorithm & Complexity

* @algorithm stack
* @time O(N logN) : 배열 정렬 O(N logN) * for loop iteration O(N) * stack 비우기 O(N)
* @memory O(N) : plans가 2차원 배열이지만 이는 입력배열이라 제외, 그 외 stack 및 answer 는 최악의 경우 O(N)

👨🏻‍💻 Logic

하라는 대로 하면 된다. 아래 과정이 반복되면서 정답 배열을 채워나간다.

1. 과제가 시작시간 순으로 주어지지 않을 수 있다는 조건이 있으므로, 먼저 과제들을 시작시간 순으로 오름차순 정렬해준다.
2. 과제가 바로 수행할 수 있는 경우에는 바로 answer 배열에 추가해주고, stack에 저장해둔 작업이 있다면 그것도 다시 꺼내어서 최대한 수행한다.
3. 과제를 바로 수행할 수 없으면 stack에 저장하고 다음으로 넘어간다.
4. 모든 과제를 차례대로 순회했으면 stack에 있는 task들을 pop하면서 answer에 전부 담아준다.

public class PGS_과제진행하기 {
    public String[] solution(String[][] plans) {
        Deque<Tuple> stack = new ArrayDeque<>();
        int plansLength = plans.length;
        int ansIdx = 0;
        String[] answer = new String[plansLength];

        String prevTask = "";
        String prevStart = "";
        String prevDuration = "";

        Arrays.sort(plans, Comparator.comparingInt(o -> getTime(o[1])));

        for (int i = 0; i < plansLength; i++) {
            String nowTask = plans[i][0];
            String nowStart = plans[i][1];
            String nowDuration = plans[i][2];

            while (i >= 1) {
                if (getEndTime(prevStart, prevDuration) > getTime(nowStart)) {
                    stack.add(new Tuple(prevTask, getDurationLeft(prevStart, prevDuration, nowStart)));
                    break;
                } else {
                    answer[ansIdx++] = prevTask;
                    prevStart = getTimeString(getEndTime(prevStart, prevDuration));
                    if (stack.isEmpty()) {
                        break;
                    }
                    Tuple stash = stack.pollLast();
                    prevTask = stash.task;
                    prevDuration = String.valueOf(stash.duration);
                }
            }

            if (i == plansLength - 1) {
                answer[ansIdx++] = nowTask;
                break;
            }
            prevTask = nowTask;
            prevStart = nowStart;
            prevDuration = nowDuration;
        }

        while(!stack.isEmpty()) {
            answer[ansIdx++] = stack.pollLast().task;
        }

        return answer;
    }
    private int getTime(String timeString) {
        StringTokenizer st = new StringTokenizer(timeString);
        int hour = Integer.parseInt(st.nextToken(":"));
        int min = Integer.parseInt(st.nextToken());
        return hour*100 + min;
    }
    private int getEndTime(String start, String duration) {
        int time = getTime(start);
        int dur = Integer.parseInt(duration);

        int hour = time / 100;
        int min = time % 100;

        int nextHr = (min + dur) / 60;
        int nextMin = (min + dur) % 60;

        hour = hour + nextHr; // 24시간 넘어가도 상관 없음. 그게 더 늦은 시간이 되어야 하니까
        min = nextMin;

        return hour*100 + min;
    }
    private String getTimeString(int time) {
        return String.valueOf(time / 100) + ":" + String.valueOf(time % 100);
    }
    private int getDurationLeft(String prevStart, String prevDuration, String nowStart) {
        // prevStart + prevDuration - nowStart;

        int prevTime = getEndTime(prevStart, prevDuration);
        int nowTime = getTime(nowStart);

        int prevHr = prevTime / 100;
        int prevMin = prevTime % 100;

        int nowHr = nowTime / 100;
        int nowMin = nowTime % 100;

        // 1230 - 1010 = 20분 + 2시간
        // 1210 - 1050 = 2시간 + -40분 = 1시간 20분

        int hrGap = prevHr - nowHr;
        int minGap = prevMin - nowMin;

        if (minGap < 0) {
            hrGap--;
            minGap += 60;
        }

        return hrGap*60 + minGap;
    }
    private class Tuple {
        String task;
        int duration;

        private Tuple(String task, int duration) {
            this.task = task;
            this.duration = duration;
        }
    }
}