백준 20665 독서실 거리두기 자바(java)

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

20665번: 독서실 거리두기

 

풀이 방법

구현, 시뮬레이션 문제이다.

좌석 배정을 위해선 예약 우선순위대로 정렬과 사용 중인 좌석 정보가 필요하다.

예약은 Reservation 클래스를 만들어 시작 시간과 끝나는 시간을 저장하고 객체로 관리할 수 있도록 하였다.

예약 정렬을 위해 우선순위 큐를 사용하여 더 빠른 예약 시간 순, 더 짧은 이용 시간 순으로 정렬할 수 있도록 하였다. 사용 중인 좌석 정보는 key 를 좌석 번호로 하는 Map<Integer, Reservation> 형의 usingSeats 을 선언하여 저장하였다.

 

풀이 흐름

• 우선순위 큐에 모든 예약을 집어 넣는다.
• 관리자가 P번 좌석을 사용할 수 있는 시간 adminTime 을 720으로 초기화하여 선언한다.
• 우선순위 큐에서 예약을 하나 꺼내어 해당 예약의 시작 시간을 현재 기준 시간으로 둔다.
• usingSeats 에서 현재 기준 시간 이전 또는 같은 시간에 만료되는 예약들을 모두 제거한다.
  • 이때, 제거되는 좌석이 P번이면 adminTime 에서 해당 예약의 사용 시간을 뺀다.
• 그 다음, 문제 규칙에 따라 좌석을 배정한다.
  • usingSeats 의 key값인 좌석 번호들을 리스트로 저장한 뒤 오름차순으로 정렬한다.
  • 가장 첫번째 좌석이 1번이 아니면 해당 좌석과 1번과의 거리를 구한다.
  • 좌석 번호 리스트를 순회하면서 좌석과 좌석 사이의 중간에 앉았을 때 거리들을 구한다.
  • 가장 마지막 좌석이 N번이 아니라면 해당 좌석과 N번과의 거리를 구한다.
  • 위 방식으로 구한 거리들 중 가장 먼 거리의 좌석을 선택한다.
• 선택된 좌석에 배정된 예약을 usingSeats 에 삽입한다.
• 예약을 모두 다 배정할 때까지 위 동작을 반복한다.
• 배정이 끝나고도 P번이 사용중이라면 마지막 P번 예약자의 사용 시간까지 adminTime 에서 뺀다.

 

알게된 점!!!

처음엔 usingSeats 에서 예약 시간이 만료된 예약을 제거할 때 HashMap 의 keySet 을 for문으로 순회하면서 그 안에서 해당 좌석을 제거해주는 방식으로 구현했었는데 java.util.ConcurrentModificationException 에러가 발생하였다. 말 그대로 동시 수정 문제로 for문으로 접근과 동시에 HashMap의 entry 를 제거하여 발생하는 문제이다. 따라서, 좌석 번호를 리스트에 저장한 뒤 리스트를 통해 좌석 번호를 순회하도록 수정하여 해결하였다.

 

 

코드

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

public class Main {

    static class Reservation implements Comparable<Reservation>{
        int start;
        int end;

        public Reservation(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Reservation o) {
            if(this.start == o.start) {
                return this.end - o.end; // 같은 시간에 예약했다면 짧은 이용 시간을 가진 순
            }
            return this.start - o.start; // 더 빨리 예약한 순
        }
    }

    static int N, T, P;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        T = Integer.parseInt(line[1]);
        P = Integer.parseInt(line[2]);
        PriorityQueue<Reservation> pq = new PriorityQueue<>();

        for(int i=0; i<T; i++) {
            line = br.readLine().split(" ");
            int sh = Integer.parseInt(line[0].substring(0, 2));
            int sm = Integer.parseInt(line[0].substring(2));
            int eh = Integer.parseInt(line[1].substring(0, 2));
            int em = Integer.parseInt(line[1].substring(2));
            pq.add(new Reservation((sh * 60) + sm, (eh * 60) + em)); // 분 단위로 바꾸어 삽입
        }

        Map<Integer, Reservation> usingSeats = new HashMap<>(); // 사용 중인 좌석
        int adminTime = 720; // 관리자 사용 시간
        while(!pq.isEmpty()) {
            Reservation reservation = pq.poll();
            int curTime = reservation.start;

            // 예약 시간이 끝난 예약자의 좌석은 제거
            List<Integer> seatNums = new ArrayList<>(usingSeats.keySet());
            for(Integer num : seatNums) {
                int start = usingSeats.get(num).start;
                int end = usingSeats.get(num).end;
                if(curTime >= end) {
                    if(num == P) { // p번 좌석인 경우
                        adminTime -= (end - start); // p번 예약자의 이용 시간만큼 뺌
                    }
                    usingSeats.remove(num);
                }
            }
            // 독서실을 이용하는 사람이 없는 경우 1번 자리 앉음
            if(usingSeats.isEmpty()) {
                usingSeats.put(1, reservation);
            } else { // 있는 경우 좌석 골라서 앉기
                int selectNum = selectSeat(usingSeats);
                usingSeats.put(selectNum, reservation);
            }
        }

        if(usingSeats.containsKey(P)) {
            adminTime -= (usingSeats.get(P).end - usingSeats.get(P).start);
        }
        System.out.println(adminTime);
    }

    public static int selectSeat(Map<Integer, Reservation> usingSeats) {
        int select = 0;
        int maxDist = Integer.MIN_VALUE;
        List<Integer> seats = new ArrayList<>(usingSeats.keySet());
        Collections.sort(seats); // 좌석 번호를 오름차순으로 정렬
        int firstSeat = seats.get(0);
        int lastSeat = seats.get(seats.size()-1);

        // 1번의 앉았을 때 가장 가까운 사람과의 거리
        if(firstSeat != 1) {
            int dist = firstSeat - 1;
            if(dist > maxDist) {
                maxDist = dist;
                select = 1;
            }
        }
        // 사람과 사람 사이에 앉을 때의 거리
        for(int i=1; i<seats.size(); i++) {
            int dist = (seats.get(i) - seats.get(i-1)) / 2;
            if(dist > maxDist) {
                maxDist = dist;
                select = seats.get(i-1) + dist;
            }
        }

        // N번에 앉았을 때 가장 가까운 사람과의 거리
        if(lastSeat != N) {
            int dist = N - lastSeat;
            if(dist > maxDist) {
                select = N;
            }
        }
        return select;
    }
}