https://www.acmicpc.net/problem/20665
20665번: 독서실 거리두기
첫 번째 줄에 독서실 좌석의 개수 N, 독서실 예약자 수 T, 민규가 좋아하는 좌석 번호 P 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100, 1 ≤ T ≤ 500, 1 ≤ P ≤ N) 다음 T 개의 줄에는 독서실 입실
www.acmicpc.net
풀이 방법
구현, 시뮬레이션 문제이다.
좌석 배정을 위해선 예약 우선순위대로 정렬과 사용 중인 좌석 정보가 필요하다.
예약은 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;
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 1106 호텔 자바(java) (1) | 2024.02.28 |
|---|---|
| 백준 2459 철사 자르기 자바(java) (0) | 2024.02.17 |
| 백준 12842 튀김 소보루 자바(java) (1) | 2024.02.15 |
| 백준 15486 퇴사 2 자바(java) (0) | 2024.02.09 |
| 백준 17822 원판 돌리기 자바(java) (1) | 2024.02.09 |