[프로그래머스] 과제 진행하기 Lv2 JAVA [우선순위큐][엄탱]

문제 링크

프로그래머스

문제 설명

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.

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

과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해 주세요.

문제 요약

간단히 요약하자면, 과제를 스케줄대로 진행하면서 위의 조건들에 맞게 진행을 하고 과제를 끝낸 순서대로 배열에 담아 return 해주면 된다.

해설

해당 문제의 핵심은 정렬과 우선순위 큐와 현재시간을 체크해 주는 것이라고 생각한다.

 

해당 문제는 설명하기 너무 어려워서 읽기 싫으신 분들을 위해 핵심 5가지만 적겠습니다.

핵심만 파악하고 문제를 풀어도 한결 수월해질 것 같습니다.

1. 처음 과제들을 시작시간 기준으로 오름차순

2. 진행해야 할 새로운 과제들은 Queue에 보관

3. 멈춰둔 과제는 우선순위 큐(PriorityQueue)에 보관(우선순위 큐는 최근 과제 순으로 정렬)

4. 현재 시간을 체크하고 멈춰둔 과제와 새로운 과제 사이를 체크해 준다.

5. 더 이상 새로운 과제가 없다면 멈춰둔 과제 보관 순으로 과제 끝내기

 

우선순위 큐가 중요한 이유

잠시 멈춰둔 과제를 관리하기 위해서 우선순위 큐가 중요하다고 생각한다.

이유는 잠시 진행 중인 과제가 끝나고 다음 진행할 과제 사이에 텀이 존재한다면 멈춰둔 과제를 진행하는데 이때 우선적으로 진행해야 하는 것이 최근에 진행했던 과제이다.

 

멈춰둔 과제의 중요한 규칙은 이렇다.

 

1. 멈춰둔 과제는 최근 진행했던 과제 순으로 진행한다. 즉, 시작 시간이 늦은 과제부터 진행을 해야 한다.

• 즉, 시작시간 기준 내림차순(혹은 다른 방법으로 최근 진행했던 순으로 정렬) 정렬이 필요하기 때문에 우선순위 큐가 좋다고 판단했다. 
• Deque를 사용해도 좋다고 판단된다. 오히려 더 좋을 수 있다고 생각된다.

2. 멈춰둔 과제가 끝나지 않는 중에 새로운 과제를 진행해야 한다면, 멈춰둔 과제는 다시 보관해야 한다.

• 다시 보관해도 시작시간이 가장 늦은 게 맨 앞에 와야 하므로 내림차순이 보장되어야 한다.
• 따라서 Queue나 Stack은 올바른 자료구조라고 생각되지 않는다.

3. 멈춰둔 과제는 다음 멈춰둔 과제와는 상관없이 다 진행한 후에 그다음 멈춰둔 과제를 꺼내와서 진행한다.

• 멈춰둔 과제만 해야 한다면, 그냥 멈춰둔 과제 순서대로 끝내면 된다.

위와 같은 이유로 우선순위 큐 혹은 Deque를 잘 사용하면 된다고 생각한다.

접근 순서

접근 순서는 아래와 같습니다.

1. 과제들을 시작 시간 기준으로 오름차순

2. 새로운 과제를 담을 Queue와 멈춰둔 과제를 담을 우선순위 큐 생성

3. 멈춰둔 과제를 담는 우선순위 큐는 과제를 진행순서 기준으로 내림차순 설정

4. Queue에 새로운 과제를 넣어준다.

5. 과제를 진행하면서 겹치는 과제가 발생하면 전에 진행하던 과제는 멈춰둔 과제를 보관하는 우선순위 큐에 보관한다. 이때 남은 시간을 저장하는 게 중요하다.

6. 새로운 과제 사이에 텀이 존재한다면, 멈춰둔 과제에서 과제를 진행한다. 단, 멈춰둔 과제를 진행 중에 새로운 과제를 해야 하면 멈춰둔 과제를 다시 우선순위 큐에 넣어준다.

7. 항상 현재시간을 체크해 준다.

• 현재시간을 체크해 줘야 멈춰둔 과제를 진행하면서 다음 새로운 과제를 해야 하는지 알 수 있다.
• 멈춰둔 과제에 있는 시작시간은 무시하고 현재시간을 기준으로 계산한다. 
• 이렇게 하지 않으면 멈춰둔 과제는 과거 시간을 갖고 있기 때문에 다시 과거 시간을 기준으로 시간을 체크하게 된다.

8. 멈춰둔 과제를 하면서 새로운 과제가 존재하지 않으면 우선순위에 보관하고 있는 순서대로 끝내면 된다.

코드

코드가 제가 봐도 읽기가 싫네요..

핵심만 알아가도 좋을 것 같습니다.

import java.util.*;

class Solution {
    public String[] solution(String[][] plans) {
        String[] answer = new String[plans.length];
        
        Arrays.sort(plans, ((x, y) -> (x[1]).compareTo(y[1])));
        
        Queue<Node> queue = new LinkedList<>();
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> y.order - x.order);
        
        for(int i = 0; i < plans.length; i++) {
            String[] plan = plans[i];
            
            String[] times = plan[1].split(":");
            
            String name = plan[0];
            int time = Integer.parseInt(times[0]) * 60 + Integer.parseInt(times[1]);
            int playtime = Integer.parseInt(plan[2]);
            
            queue.offer(new Node(name, time, playtime, i));
        }
        
        int idx = 0;
        int nowTime = 0;
        
        while(!queue.isEmpty()) {
            Node cur = queue.poll();
            
            if (queue.isEmpty()) {
                answer[idx++] = cur.name; 
                continue;
            }
            
            Node next = queue.peek();
            
            if (cur.time + cur.playtime > next.time) {
                int num = next.time - cur.time;
                pq.offer(new Node(cur.name, cur.time + num, cur.playtime - num, cur.order));
                nowTime = next.time;
            } else if (cur.time + cur.playtime == next.time) {
                answer[idx++] = cur.name;
                nowTime = next.time;
            } else {
                answer[idx++] = cur.name;
                nowTime = cur.time + cur.playtime;
                
                while(!pq.isEmpty()) {
                    Node pqCur = pq.poll();
                    
                    if (nowTime + pqCur.playtime > next.time) {
                        int num = next.time - nowTime;
                        pq.offer(new Node(pqCur.name, pqCur.time + num, pqCur.playtime - num, pqCur.order));
                        nowTime = next.time;
                        break;
                    } else if (nowTime + pqCur.playtime == next.time) {
                        answer[idx++] = pqCur.name;
                        nowTime = next.time;
                        break;
                    } else {
                        answer[idx++] = pqCur.name;
                        nowTime += pqCur.playtime;
                    }
                }
            }
        }
        
        while(!pq.isEmpty()) {
            answer[idx++] = pq.poll().name;
        }
        
        return answer;
    }
}

class Node {
    String name;
    int time;
    int playtime;
    int order;
    
    public Node (String name, int time, int playtime, int order) {
        this.name = name;
        this.time = time;
        this.playtime = playtime;
        this.order = order;
    }
}