백준 27112 - 시간 외 근무 멈춰! (자바 - 그리디)

https://www.acmicpc.net/problem/27112

27112번: 시간 외 근무 멈춰!

 

* 문제 요약

오늘도 여러 체계의 개발 임무를 열심히 수행중인 준민이에게 갑자기 새로운 개발 프로젝트가 들어왔다.

해당 개발 프로젝트는 총 N개의 작업으로 이루어져 있으며, 각 작업은 ti 의 근무일이 필요하며, 개발 프로젝트가 시작한 이후 di 일이 지나기 전에 끝내야 한다.

그러나 평시 근무만으로는 모든 N개의 작업을 시간 내에 끝내기 힘들어 보였던 준민이는 개인 정비시간을 포기하며 시간 외 근무를 하고자 한다.

개발 프로젝트는 월요일부터 시작하며, 평시 근무는 월요일부터 금요일 까지만 진행한다. 시간 외 근무는 요일과 관계없이 매일 최대 한 번씩만 진행할 수 있으며, 시간 외 근무를 1회 진행하며 1일치 업무를 끝마칠 수 있다.

 

준민이는 이를 토대로 효과적인 일정을 짜고 싶었지만, 이미 프로젝트로 너무 바빠진 준민이는 일정을 짤 시간조차 없는 상태이다. 바쁜 준민이를 위해 모든 작업을 마감 기한전까지 끝내고자 할 때 해야 하는 최소 시간 외 근무 일수를 알려주자.

 

* 입력

첫 번째줄에 작업의 갯수 N이 주어진다. (1 <= N <= 100,000)

두 번째 줄부터 N + 1 번째 줄까지, 각 작업의 마감 기한을 나타내는 정수 di 와 작업에 걸리는 시간을 나타내는 정수 ti 가 공백으로 구분되어 주어진다. (1 <= di, ti <= 100,000)

 

* 출력

모든 작업을 마감 기한 전까지 끝낼 수 있도록 하는 최소 시간 외 근무일수를 출력한다.

만약 어떻게 해도 마감 기한 전까지 모든 작업을 끝낼 수 없다면 -1을 출력한다.

 

* 예시 첨부

 

* 해결 과정

입력받은 정보들은 마감날짜를 기준으로 오름차순 정렬되게끔 우선순위 큐에 저장해주었다.

마감날짜가 평일인지 주말인지는 다음과 같은 절차로 로직을 설계했다.

1. 마감날짜가 가장 늦는 날짜 크기만큼 int 배열 생성

2. 배열의 처음부터 끝까지 반복문을 수행하며, 처음 5번 반복되는 동안 0, 그 이후 2번 반복되는 동안 Integer.MIN_VALUE 를 저장시켜 주면서 인덱스 별로 평일, 주말 구분

주말의 경우 Integer.MIN_VALUE, 평시 근무일인 경우 0에 해당된다.

 

시간 외 근무횟수를 최소화 시켜야 하기 때문에 일단 평시 근무만으로 해결하는 경우를 우선으로 두었으며, 평시 근무 시작점, 시간 외 근무 시작점 총 두 가지 인덱스를 동시에 다루어주었다.

이후는 아래와 같이 로직을 수행했다.

1. 큐에서 가장 앞에있는 업무를 추출하여 마감날짜와 필요한 근무일수를 확인

2. 평시 근무 시작점부터 마감날짜에 해당하는 인덱스까지 주말을 제외하고 업무처리가 가능한지 반복문을 통해 확인

3. 만약 평시 근무만으로 업무 완료가 불가능할 경우 요일과 상관없이 시간 외 근무까지 확인, 이때 정답변수 result 값 1씩 증가

4. 시간 외 근무로도 마감 날짜까지 해결이 안될 경우 -1 출력

5. 업무가 모두 가능한 경우 result 값 출력

 

처음 풀 때 시간 외 근무까지 주말 업무를 제외시켜 놓고 풀다가 잘 안 풀려서 고민하던 중, 문제를 다시 한 번 읽어보니 시간 외 근무를 할 때는 요일에 상관없이 매일 가능하다는 문구를 보고 즉시 적용해서 해결한 문제.

문제를 자세히 읽었다면 더 빨리 해결할 수 있었을 텐데 이 부분은 고쳐야 할 점이라고 생각한다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());

        PriorityQueue<Work> prior = new PriorityQueue<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < count; i++) {
            String[] input = br.readLine().split(" ");
            int deadLine = Integer.parseInt(input[0]);
            int require = Integer.parseInt(input[1]);

            max = Math.max(max, deadLine);
            prior.offer(new Work(deadLine, require));
        }

        int[] check = new int[max + 1];
        int normal = 0;
        int week = 0;
        for (int i = 1; i < check.length; i++) {
            if (normal < 5) {
                // 평일
                normal++;
            } else if (normal >= 5 && week < 2) {
                check[i] = Integer.MIN_VALUE; // 주말
                week++;
            } else {
                // 주말이 지난 후 다시 평일
                normal = 0;
                week = 0;
                normal++;
            }
        }

        int normalStart = 1; // 평시 근무 시작점
        int overStart = 1; // 시간 외 근무 시작점
        int result = 0;
        while (!prior.isEmpty()) {
            Work work = prior.poll();
            int deadLine = work.deadLine;
            int require = work.require;
            // 평시근무 만으로 마감일까지 맞출 수 있는지 확인
            while (require > 0 && normalStart <= deadLine) {
                if (check[normalStart] == Integer.MIN_VALUE) {
                    normalStart++;
                } else {
                    normalStart++;
                    require--;
                }
            }
            // 로직 상 시간 외 근무 날짜가 평일 근무 날짜를 초과하는 경우는 없음
            // 평시 근무만으로 업무를 모두 완료하지 못한 경우 '요일과 상관없이' 시간 외 근무 확인
            if (require > 0) {
                while (require > 0 && overStart <= deadLine) {
                    // 해당 일자 시간 외 근무 수행
                    overStart++;
                    require--;
                    result++;
                }
            }
            // 시간 외 근무로도 마감 날짜내에 해결이 안될 경우
            if (require > 0) {
                bw.write(-1 + "\n");
                bw.flush();
                bw.close();
                br.close();
                return;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

class Work implements Comparable<Work> {
    int deadLine;
    int require;

    public Work(int deadLine, int require) {
        this.deadLine = deadLine;
        this.require = require;
    }

    @Override
    public int compareTo(Work arg0) {
        return this.deadLine - arg0.deadLine;
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 매 업무마다 다른 업무를 처리한 이후의 업무시작 날짜를 기준으로도 평시 근무로 마감기한을 맞출 수 있는지 확인하고 그렇지 않을 경우 시간 외 근무를 하며 마감기한을 맞출 수 있는지 확인한다.

선택된 해답이 조건을 만족하는지 검사한다. -> 모든 업무에 대한 처리가 될 때까지 필요한 시간 외 근무일수를 완전히 산출해 낼 수 없으므로 계속 반복문을 수행한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘에 해당된다.