[ BOJ ][JAVA][20665] 독서실 거리두기

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

20665번: 독서실 거리두기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	538	98	86	22.051%

문제

코로나 바이러스로 사회적 거리두기가 한창이다. 하지만 이러한 시국 이전에도 거리두기가 잘 지켜지던 곳이 있었으니... 바로 독서실이다.

독서실에서 관리자로 근무 중이던 민규는 놀라운 사실을 발견했다. 사람들은 항상 서로 더 멀리 앉으려고 노력한다는 것이었다.

민규는 이러한 사실을 관찰하여 잘 정리해보았다.

1. 사람들은 가장 가까이에 앉아있는 사람이 가장 먼 자리를 선호한다. 만약 독서실을 이용하는 사람이 없다면 좌석번호 1번 자리를 가장 선호한다.
2. 1번 규칙으로 비교할 수 없다면, 가장 먼 좌석들 중에서 좌석 번호가 가장 작은 자리를 선호한다.

독서실 관리자로 오래 근무한 민규에게는 선호하는 좌석이 있다. 하지만 민규는 매우 소심하기 때문에, 사람들이 본인 때문에 이용하고자하는 자리를 이용하지 못하는 일은 피하고 싶다.

민규가 근무하는 독서실은 09:00 부터 21:00 까지 운영되며, 철저히 예약제로 운영되기 때문에 민규는 사람들이 언제부터 언제까지 독서실을 이용하는지 알 수 있다.

이러한 정보를 토대로, 민규는 자신이 선호하는 자리를 얼마나 이용할 수 있는지 계산해보고자 한다.

입력

첫 번째 줄에 독서실 좌석의 개수 N, 독서실 예약자 수 T, 민규가 좋아하는 좌석 번호 P 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100, 1 ≤ T ≤ 500, 1 ≤ P ≤ N)

다음 T 개의 줄에는 독서실 입실 시간, 독서실 퇴실 시간이 HHMM HHMM 형태로 입력된다.

(0900 ≤ HHMM ≤ 2100, 0910 0900와 같이 퇴실 시간이 입실 시간보다 빠른 경우는 없다)

출력

민규가 선호하는 좌석을 이용할 수 있는 시간이 총 몇분인지 출력하시오.

제한

독서실의 모든 좌석은 비어있는 상태로 시작한다.

독서실 예약이 같은 시각에 시작된다면 짧은 이용시간을 가진 사람을 먼저 앉힌다.

독서실 예약 리스트에 있는 예약자들이 좌석이 없어서 못 앉는 상태는 존재하지 않는다.

민규는 선호하는 좌석을 얼마나 이용할 수 있는지 계산하고 싶어하는 것이기 때문에 예약인원들이 자리를 이용하는 것에 영향을 주지 않는다.

예제 입력 1

5 6 1
0915 0930
0940 2040
0910 0920
2040 2050
2043 2047
2044 2046

예제 출력 1

40

코드

/**
 * BOJ 20665 독서실 거리두기 : Gold 5
 * 구현, 시뮬레이션
 */
import java.io.*;
import java.util.*;

public class p20665 {
    static class Time implements Comparable<Time> {
        int start, end;
        public Time(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public int compareTo(Time o) {
            if (start != o.start) {
                return start - o.start;
            }
            return end - o.end;
        }
    }
    static int first;
    static int last; 
    static int n, t, p;
    static Time[] time;
    static boolean[][] isSeated;
    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()); // 민규가 좋아하는 좌석 번호
        time = new Time[t];
        first = hour2Min("9");
        last = hour2Min("21");

        isSeated = new boolean[last + 100][n + 1]; // ex) isSeated[600][3] = true; 600분에 2번좌석이 차있다.

        int start, end;
        for (int i = 0; i < t; i++) {
            st = new StringTokenizer(br.readLine());
            String from = st.nextToken();
            start = 0;
            start += hour2Min(from.substring(0, 2));
            start += Integer.parseInt(from.substring(2, 4));

            String to = st.nextToken();
            end = 0;
            end += hour2Min(to.substring(0, 2));
            end += Integer.parseInt(to.substring(2, 4));

            time[i] = new Time(start, end);
        }

        // 예약을 먼저 온 순번대로 뽑아야 하기 때문에 정렬의 과정이 필요하다.
        Arrays.sort(time);

        // 독서실의 남은 자리를 체크하고 정책에 따라서 배정한다.
        for (int i = 0; i < t; i++) {
            Time cur = time[i];

            int s = cur.start;
            int e = cur.end;
            int seat = findSeat(s);

            for (int j = s; j < e; j++) {
                isSeated[j][seat] = true;
            }
        }

        int answer = 0;
        for (int i = first; i < last; i++) {
            if (!isSeated[i][p]) {
                answer++;
            }
        }
        System.out.println(answer);
    }

    static int hour2Min(String s) {
        int num = Integer.parseInt(s);
        return num * 60;
    }

    // min 시각에 앉을 수 있는 자리 반환
    static int findSeat(int min) {
        int maxDist = 0;
        int pos = 0;

        for (int i = 1; i <= n; i++) {
            if (!isSeated[min][i]) {
                int dist = getDistance(min, i);
                if (maxDist < dist) { // 가장 멀리 앉을 수 있는 곳을 반환 할 거야
                    maxDist = dist;
                    pos = i;
                }
            }
        }
        return pos;
    }

    // min 시각에 num의 입장에서 가장 가까이 있는 좌석의 거리 ; 이 거리가 제일 길어야 해!
    static int getDistance(int min, int num) {
        int minDist = 110;
        for (int i = 1; i <= n; i++) {
            if (i == num) continue;
            if (isSeated[min][i]) {
                int dist = Math.abs(i - num);
                if (minDist > dist) {
                    minDist = dist;
                }
            }
        }
        return minDist;
    }
}