문제

풀이 과정

요약

priority queue 를 활용한 문제.
구현은 어렵지 않으나 시간 초과를 유도하는 부분을 조심하자.

상세

1. 먼저 사원 정보를 저장할 공간을 만들자. 나의 경우에는 클래스를 사용했다.
2. 각 줄을 나타내는 공간이 필요하다. 나의 경우에는 리스트 배열을 생성하여 LinkedList 를 넣어줬다.
   • LinkedList 를 채택한 이유는 삽입, 삭제 시 시간 복잡도가 $O(1)$ 이기 때문, 맨 처음 애들만 계속 뽑아내기 때문에 탐색 역시 $O(1)$이다. 메모리 제한이 왕창 크게 한거로 봐서는 그냥 Queue 배열 쓰라고 낸 문제인듯 하다. (근데 Queue 도 결국 LinkedList 잖아?!!)
3. 생성한 줄 LinkedList 에 사원이 서 있도록, 사원 클래스를 생성하여 집어넣자. 단, 데카인 경우에는 확인을 위해 true 를 넣어주자.
4. 우선순위에 맞게 pq 를 생성해주자.
5. 각 LinkedList 마다 가장 선두에 있는 사원들을 pq에 초기값으로 넣은 후, 사원 수 N 만큼 반복문을 실행한다. 우선순위 큐에 현재 가장 선두의 사원을 뽑아, 데카인지를 확인한 후 맞다면 지금까지의 cnt 를 출력한다. 아니라면 cnt 를 1개 더하고, 해당 LinkedList 에서 0번째를 삭제. 그리고, 다음 사원을 pq 에 넣으면 된다.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Employee {
        // D = 근무일수
        // H = 화장실 급한 정도
        // L = 현재 라인
        int D, H, L;
        public boolean me;

        Employee(int D, int H, int L, boolean me) {
            this.D = D;
            this.H = H;
            this.L = L;
            this.me = me;
        }
    }

    static int N, M, K;
    static List<Employee> list[];

    // 골드 4
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        K = Integer.parseInt(stk.nextToken());

        list = new LinkedList[M];
        for (int i = 0; i < M; i++) list[i] = new LinkedList<>();

        int idx = 0;
        int cnt = N;
        while (--cnt >= 0) {
            stk = new StringTokenizer(br.readLine());
            int L = idx++ % M;
            boolean check = K-- == 0;
            list[L].add(new Employee(Integer.parseInt(stk.nextToken()), Integer.parseInt(stk.nextToken()), L, check));
        }

        cnt = 0;
        PriorityQueue<Employee> pq = new PriorityQueue<>((o1,o2) -> o1.D == o2.D ? o1.H == o2.H ? o1.L - o2.L : o2.H - o1.H : o2.D - o1.D);

        for (int j = 0; j < M; j++) if (list[j].size() > 0) pq.add(list[j].get(0));

        for (int i = 0; i < N; i++) {
            Employee currE = pq.poll();
            if (currE.me) {
                System.out.println(cnt);
                return;
            } else {
                cnt++;
                list[currE.L].remove(0);
                if (list[currE.L].size() > 0) pq.add(list[currE.L].get(0));
            }
        }
    }
}