프로그래머스 - 과제 진행하기

문제 링크 ▶︎ 과제 진행하기

문제 파악

처음에 주어진 과제에 대해서 시작 시간과 잔여 시간에 따라서 큐에 저장해야할 것이고, 강제 중지된 과제들을 담을 스택을 따로 만들어야한다. 강제 중지된 과제들을 스택에 담는 이유는 문제에서 보면 마지막에 중지된 과제를 먼저 수행한다고 했기때문이다. 그래서 시간을 int로 비교하는 것과 큐와 스택을 잘 쓰면 풀 수 있을 것 같았다. 그리고 과목 문자와 시작 시간과 잔여 시간을 모두 비교하고 저장해야하므로 그냥 과목에 대한 클래스를 만들어서 쓰면 편할 것 같았다.

접근 방법

1. 과제에 대한 정보 클래스인 obj에 과목 이름 subject랑 시작시간을 int로 변환한 정수와 잔여시간에 대한 정수를 저장한다. 그리고 시작시간은 time 메서드에서 split으로 나눠 분으로만 계산한다.

2. 우선순위큐 data에 모든 시간을 저장하는데 이것은 시작시간이 빠른 순으로 저장한다. 그리고 강제중지된 과제들을 담을 stack도 만들어둔다.

3. 시작시간이 빠른 순서대로 data에서 과제를 빼고 다음 시작시간이 빠른 과제와 시간을 비교해서 강제중지될 상황이면 강제중지하고 해당 과제를 stack 잔여시간을 계산해서 넣어준다. 만약 과제가 잘 수행된다면 정답 배열에 해당 과제 과목이름을 넣고, stack에 강제중지된 과제를 수행하거나 stack이 비어있다면 다음 과제를 바로 수행한다.

4. 모든 과제를 다 수행하고 나면, stack에 남은 과제들을 순서대로 수행해야하는데 이 순서는 그냥 stack에서 pop되는 순서대로 저장하면된다. 정답 배열은 길이를 정해놓고 저장하기 때문에 idx를 매번 잘 증가시켜야한다.

코드 구현

import java.util.*;
class Solution {
    public String[] solution(String[][] plans) {
        String[] answer = new String[plans.length];
        PriorityQueue<obj> data = new PriorityQueue<>((o1, o2) -> o1.time - o2.time);
        for (int i=0; i<plans.length; i++) {
            data.add(new obj(plans[i][0], time(plans[i][1]), Integer.parseInt(plans[i][2])));
        }
        Deque<obj> stack = new ArrayDeque<>();
        int idx = 0;
        while (!data.isEmpty()) {
            obj out = data.remove();
            if(!data.isEmpty()) {
                int diff_time = data.peek().time - out.time;
                System.out.println(diff_time);
                if(diff_time >= out.remain) {
                    answer[idx++] = out.subject;
                    diff_time -= out.remain;
                    while (!stack.isEmpty()) {
                        obj other = stack.pop();
                        if (other.remain > diff_time) {
                            other.remain -= diff_time;
                            stack.push(other);
                            break;
                        } else {
                            diff_time -= other.remain;
                            answer[idx++] = other.subject;
                        }
                    }
                } else {
                    out.remain -= diff_time;
                    stack.push(out);
                }
            } else {
                answer[idx++] = out.subject;
            }
        }
        while(!stack.isEmpty()) {
            obj out = stack.pop();
            answer[idx++] = out.subject;
        }
        return answer;
    }
    public int time(String time) {
        String[] arr = time.split(":");
        int t = 0;
        t += Integer.parseInt(arr[0]) * 60;
        t += Integer.parseInt(arr[1]);
        return t;
    }
    class obj {
        String subject;
        int time;
        int remain;
        
        public obj(String subject, int time, int remain) {
            this.subject = subject;
            this.time = time;
            this.remain = remain;
        }
    }
}

개선 사항

그냥 정답 배열을 만들지 않고 List 으로 추가하고 나중에 배열로 변경했으면 idx에 대한 신경을 쓰지 않아도 돼서 더 편했을 것 같다.