[백준]6068: 시간 관리하기 - JAVA

[백준]6068: 시간 관리하기

6068번: 시간 관리하기

풀이

🪑 자료구조를 사용하여 풀었다. 비슷한 유형의 문제가 많을 것 같은 문제였다.

 

📝 문제를 정리해 보자!

• 해야 할 일이 존재한다.
• 일을 하는데 필요한 시간과 끝내야 하는 시간이 주어진다.
• 가장 늦게 일어나도 되는 시간을 구한다.

 

 

🔧 문제를 풀어 보자!

1. 입력받은 할 일을 끝내야 하는 시간을 기준으로 오름차순 정렬하여 우선순위큐에 담는다.
2. 우선순위큐에서 하나씩 할 일의 정보를 꺼낸다.
3. 총 업무 시간을 누적하여 더해주고, 현재 업무를 끝내야 하는 시간에서 총 업무 시간을 뺀 값 중의 최소값을 찾는다.
4. 중간에 총 업무 시간이 현재 업무를 끝내야 하는 시간보다 크다면 제 시간에 일을 끝낼 수 없다는 의미이므로 -1을 출력한다.

 

 

🔹 할 일을 끝내야 하는 시간을 기준으로 오름차순 정렬하여 우선순위큐에 담는다.

• 먼저 끝내야 할 일을 먼저 처리해 주기 위함이다.

 

 

🔹 우선순위큐에서 하나씩 할 일의 정보를 꺼낸다.

• 순서대로 할 일을 진행해 준다는 의미이다.

 

🔹 총 업무 시간을 누적하여 더해주고, 현재 업무를 끝내야 하는 시간에서 총 업무 시간을 뺀 값 중의 최소값을 찾는다.

• 총 업무 시간은 지금까지 업무를 진행한 총 시간을 의미하므로 누적하여 더해준다.
• 현재 업무를 끝내야 하는 시간에서 총 업무 시간을 빼면 업무를 시작해야 하는 시간(적어도 이 시간에는 업무를 시작해야 하는 시간)을 알 수 있다.
• 해당 시간 중에서 최소 값을 찾아주면 그 값이 가장 늦게 일어날 수 있는 시간이 된다.

 

 

🔹 총 업무 시간이 현재 업무를 끝내야 하는 시간보다 크다면 제 시간에 일을 끝낼 수 없다.

• 이럴 때는 -1을 출력해 주면 된다.

 

코드

//6068: 시간 관리하기
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
 
        PriorityQueue<Node> work_list = new PriorityQueue<>((o1, o2) -> o1.end_time - o2.end_time);
        for(int i = 0; i < n ; i++) {
            String str = bf.readLine();
            StringTokenizer st = new StringTokenizer(str);
            int t = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            work_list.add(new Node(t, e));
        }
        //입력 끝
 
        int total_time = 0;
        int min_start_time = Integer.MAX_VALUE;
        boolean isDone = true;
        while(!work_list.isEmpty()) {
            Node current = work_list.poll();
            total_time += current.time;
            min_start_time = Math.min(min_start_time, current.end_time - total_time);
            if(total_time > current.end_time) {
                isDone = false;
                break;
            }
        }
        if(!isDone) System.out.println("-1");
        else System.out.println(min_start_time);
    }
 
    public static class Node {
        int time, end_time;
 
        public Node(int time, int end_time) {
            this.time = time;
            this.end_time = end_time;
        }
    }
}