[ 백준 / BOJ 20665 ] 독서실 거리두기 ( 자바 / JAVA )

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

20665번: 독서실 거리두기

 

문제

---

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

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

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

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

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

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

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

입력

---

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

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

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

출력

---

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

 

제한

---

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

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

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

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

예제

---

입력 

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

출력

40

09:00 ~ 09:10 시간에는 1번 자리가 비워져 있으므로 민규가 앉을 수 있다. = 10분

09:10 에는 3번 예약자가 와서 규칙에 따라 1번 좌석을 이용한다.

09:15 에는 1번 예약자가 와서 규칙에 따라 5번 좌석을 이용한다.

3번 예약자는 09:20에 퇴실이므로 민규는 09:20 ~ 09:40 시간에 1번 좌석에 앉을 수 있다. = 20분

09:30 에는 1번 예약자가 사용을 완료하여 퇴실한다.

09:40 에는 2번 예약자가 와서 규칙에 따라 1번 좌석을 이용한다.

20:40 에는 2번 예약자가 사용을 완료하여 퇴실하고 이어서 4번 예약자가 20:40 부터 1번 좌석사용을 시작한다.

20:43 에는 5번 예약자가 와서 규칙에 따라 5번 자리를 이용한다.

20:44 에는 6번 예약자가 와서 규칙에 따라 3번 자리를 이용한다.

20:46 에는 6번 예약자가 사용을 완료하여 퇴실하고 20:47 에는 5번 이용자가 사용을 완료하여 퇴실한다.

20:50 에는 4번 예약자가 사용을 완료하여 퇴실하므로 민규는 20:50 ~ 21:00 시간에 1번 좌석에 앉을 수 있다. = 10분

10 + 20 + 10 = 40

풀이

---

시뮬레이션(구현)문제로 가장 취약한 문제 ‼️

이 문제에서 관건은 자리 찾기 인 듯 ‼️

 

findSeat(int hour, int min); 

👉 for 문을 돌면서 각 자리에 예약이 없다면, findMinSeatDist로 구한 가장 가까이 앉아있는 사람과의 거리가 가장 먼 자리를 구한다

findMinSeatDist(int hour, int min, int i);

👉 i 번째 좌석에서 가장 가까이 앉아있는 사람과의 거리를 구한다.

 

boolean isSeat[hour][min][seat]

👉 hour:min 시간에 seat 자리에 사람이 앉아있는지 여부 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main_BOJ_20665_독서실거리두기 {

    static class time{
        int hour;
        int min;

        time(int hour, int min){
            this.hour = hour;
            this.min = min;
        }
    }

    static class timePair implements Comparable<timePair>{
        time start;
        time end;

        timePair(time start, time end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(timePair o) {
            int result = this.start.hour - o.start.hour;
            if(result == 0)
                result = this.start.min - o.start.min;
            if(result == 0)
                result = this.end.hour - o.end.hour;
            if(result == 0)
                result = this.end.min - o.end.min;

            return result;
        }
    }

    static int N, T, P;
    static List<timePair> timeList = new ArrayList<>();
    static boolean[][][] isSeated;

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

        N = Integer.parseInt(stringTokenizer.nextToken());  // 좌석 개수
        T = Integer.parseInt(stringTokenizer.nextToken());  // 예약자 수
        P = Integer.parseInt(stringTokenizer.nextToken());  // 좋아하는 좌석 번호

        isSeated = new boolean[24][60][N+1];

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

            time startTime = new time(start / 100, start % 100);
            time endTime = new time(end / 100, end % 100);

            timeList.add(new timePair(startTime, endTime));
        }

        Collections.sort(timeList);

        solve();
    }

    private static void solve() {
        for(timePair time : timeList){
            int startHour = time.start.hour;
            int startMin = time.start.min;
            int endHour = time.end.hour;
            int endMin = time.end.min;
            int seat = findSeat(startHour, startMin);

            for(int hour = startHour ; hour <= endHour ; hour++){
                if(startHour == endHour){
                    for(int min = startMin ; min < endMin ; min++){
                        isSeated[hour][min][seat] = true;
                    }
                    break;
                }

                if(hour == startHour){
                    for(int min = startMin ; min < 60 ; min++){
                        isSeated[hour][min][seat] = true;
                    }
                }
                else if(hour == endHour){
                    for(int min = 0 ; min < endMin ; min++){
                        isSeated[hour][min][seat] = true;
                    }
                }
                else{
                    for(int min = 0 ; min < 60 ; min++){
                        isSeated[hour][min][seat] = true;
                    }
                }
            }
        }

        int ans = 0;
        for(int hour = 9; hour < 21 ; hour++){
            for(int min = 0 ; min < 60 ; min++){
                if(!isSeated[hour][min][P]) 
                    ans++;
            }
        }
        
        System.out.println(ans);
    }

    private static int findSeat(int hour, int min) {
        int maxDist = 0;
        int idx = -1;

        for(int i = 1; i <= N; i++){
            if(!isSeated[hour][min][i]){
                int dist = findMinSeatDist(hour, min, i);
                if(dist > maxDist){
                    maxDist = dist;
                    idx = i;
                }
            }
        }
        return idx;
    }

    // 가장 가까이에 앉아있는 좌석거리 찾기
    private static int findMinSeatDist(int hour, int min, int i) {
        int minDist = 101;
        for(int next = 1; next <= N ; next++){
            if(next == i)   continue;
            if(isSeated[hour][min][next]){
                int d = Math.abs(i - next);
                if(d < minDist)
                    minDist = d;
            }
        }
        return minDist;
    }
}