독서실 거리두기 - 20665번

---

풀이 방법

그냥 차근차근 구현을 통해 풀이했다. 먼저 입력받은 시간을 분으로 변경해서 배열에 저장했다.

정렬을 통해 순서를 정해주고 우선순위 큐를 통해 꺼내는 순서를 정해주었다. 

큐에 넣고 꺼낼 때마다 가장 멀리 있는 좌석을 선택해서 관리자가 들어갈 수 있는지 확인해주었다.

 

내 코드

package com.company;

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

public class Main {
    static int N, T, P;
    static int[][] arr;
    static int[] seat;
    static PriorityQueue<Man> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        arr = new int[T][2];
        seat = new int[N + 1];

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int finish = Integer.parseInt(st.nextToken());

            arr[i][0] = (start / 100) * 60 + (start % 100);
            arr[i][1] = (finish / 100) * 60 + (finish % 100);
        }

        Arrays.sort(arr, ((o1, o2) -> {
            if (o1[0] < o2[0])
                return -1;
            else if (o1[0] == o2[0] && o1[1] - o1[0] < o2[1] - o2[0])
                return -1;

            return 1;
        }));

        int time = 540;
        int answer = 0;


        for (int i = 0; i < arr.length; i++) {
            while (!pq.isEmpty() && arr[i][0] >= pq.peek().getFinish()) {
                Man m = pq.poll();
                findSeat();
                if (seat[P] != 0 && time == 0) {
                    time = m.getFinish();
                }
            }
            pq.add(new Man(arr[i][0], arr[i][1], findSeat()));
            findSeat();

            if (seat[P] == 0 && time != 0) {
                answer += arr[i][0] - time;
                time = 0;
            }
        }

        while (!pq.isEmpty()) {
            Man m = pq.poll();
            findSeat();
            if (seat[P] != 0 && time == 0) {
                time = m.getFinish();
            }
        }

        if (time != 0) {
            answer += 1260 - time;
        }

        System.out.println(answer);
    }

    static int findSeat() {
        int max = 1;
        int index = 1;
        Arrays.fill(seat, 100);

        for (Man m : pq) {
            int x = m.getSeat();
            for (int j = N; j >= 1; j--) {
                seat[j] = Math.min(Math.abs(j - x), seat[j]);
            }
        }

        for (int i = seat.length - 1; i > 0; i--) {
            if (seat[i] == 100)
                continue;
            if (max <= seat[i]) {
                max = seat[i];
                index = i;
            }
        }

        return index;
    }

}

class Man implements Comparable<Man> {
    private int start;
    private int finish;
    private int seat;

    @Override
    public int compareTo(Man other) {
        if (this.finish < other.finish) {
            return -1;
        }
        return 1;
    }

    Man(int start, int finish, int seat) {
        this.start = start;
        this.finish = finish;
        this.seat = seat;
    }

    public int getFinish() {
        return finish;
    }

    public int getSeat() {
        return seat;
    }

    public int getStart() {
        return start;
    }
}