[JAVA] 백준 3078 좋은 친구

 

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

 

문제분석

각 업무의 [소모 시간, 마감 시간]을 받아 마감 시간이 늦은 순으로 정렬한 뒤, 가장 늦게 시작할 수 있는 시점을 역으로 계산하는 그리디 전략이다. 가장 늦은 마감 시간을 start로 두고, 각 업무를 순서대로 보면서 현재 시작 가능 시점이 해당 업무의 마감 시간보다 늦다면 단순히 소모 시간을 빼고, 더 이르다면 그 업무의 마감 직전으로 당긴 뒤 소모 시간을 빼는 방식으로 갱신한다. 이는 모든 일을 마감 시간 내에 끝내면서 시작 시점을 최대한 늦추려는 전략이며, 모든 업무를 처리한 뒤 start가 음수면 불가능하므로 -1을, 그렇지 않으면 계산된 start를 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int K; // 등수 차이, K 등수 차이를 넘으면 좋은 친구 탈락
    static long result = 0; // 좋은 친구 수

    // 학생 글자수별 queue 운영(2글자 ~ 20글자 이므로, 총 19개면 됨). idx는 0 은 2글자, 1은 3글자..
    static ArrayDeque<Integer>[] q; // 각 q별 저장하는 값은 "해당 친구 등수"

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 반 학생의 이름(성적순) 수
        K = Integer.parseInt(st.nextToken());

        q = new ArrayDeque[19];
        for (int i = 0; i < 19; i++) {
            q[i] = new ArrayDeque<>();
        }

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            int len = s.length();
            count(i, len);
        }
        System.out.println(result);
    }

    static void count(int prizeNum, int len) {
        int qIdx = len - 2;// q는 0부터 시작하기 때문에, 2글자 이름이면 0
        if (q[qIdx].size() == 0) {
            q[qIdx].offer(prizeNum);
        } else {
            while (!q[qIdx].isEmpty()) {
                if (prizeNum - q[qIdx].peek() > K) { // q의 맨 앞 친구와 K 이상 차이나는 경우
                    q[qIdx].poll();
                } else { // q 안에 좋은 친구만 남은 경우
                    break;
                }
            }
            result += q[qIdx].size();
            q[qIdx].offer(prizeNum);
        }
    }
}