백준 9203 호텔 예약 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/9203

(1) 조건 분석 📊

2. 코드가 나오기까지 🛠️

1. 년,월,일,시를 모두 분으로 바꾼다.
1. 년과 월은 해당 기간안에 윤년이 끼어있을 수 있으므로, 윤년 계산을 해야한다.
2. 시작시간 ~ 끝시간 모두 가지는 클래스를 만들어 저장한다.

2. 시작 시간 오름차순으로 정렬해서 List에 저장한다.

3. 이후 끝 시간 오름차순으로 저장하는 PriorityQueue 를 만든다. 이후 list를 작은순부터 순회하며 다음을 진행한다.
1. 큐가 비어있으면 큐에 호텔 예약 값 넣기
2. 큐가 하나라도 차있으면 큐의 peek() 종료 시간과 과 현재 집어넣을 값의 시작 시간을 비교
1. 큐 종료 시간 > 넣을 값의 시작 시간: 현재 호텔에 차있는 객실 중 새로 뺄 값은 없다. 따라서 넣을 값 삽입
2. 큐 종류 시간 < 넣을 값 시작 시간: 호텔에 이미 이용이 종료된 방이 있다. 큐의 종료 시간 > 넣을 값의 시작 시간이 될 떄까지 poll() 한다.

4. 큐에 들어있는 값이 동시간 대에 같이 배정되어야 하는 호텔 예약 수이다. 따라서 답이 되는 max 값을 만들어서 매번 이 큐 사이즈와 최대값을 비교후 갱신한다.

(1) 시간복잡도 분석 ⏳

• 호텔 예약 정렬해서 넣기: $O(N \times \log{N})$

• 호텔 순회하며 매 시점마다 차있는 객실 수 세기: $O(N\times\log{N})$

3. 코드 🌐

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



public class Main {
    static int N;
    static int [] nums;
    static HashMap<Integer, Boolean> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nums = new int [N];
        for(int i = 0; i < N; i++){
            nums[i] = Integer.parseInt(br.readLine());
        }        Arrays.sort(nums);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                map.put(nums[i]+nums[j], true);
            }        }
        for(int i = N-1; i >= 0; i--){
            for(int c = 0; c < N; c++){
                if(map.getOrDefault(nums[i] - nums[c], false)){
                    System.out.println(nums[i]);
                    return;
                }
            }
        }
    }
}

4. 트러블 슈팅 or 배운 점📝