CODEKATA 115 ~ 116

115번 호텔 대실

/*
문제 분석
1. 정보
    - 최소한의 객실만을 사용하여 예약 손님들을 받으려 한다.
    - 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있다.
2. 목표
    - 예약 시간이 담긴 book_time이 매개변수로 주어질 때, 필요한 최소 객실의 수를 반환
3. 제약 조건
    - 1 <= book_time의 길이 <= 1000

풀이
1. 아이디어
    - 우선순위 큐 사용
        - :를 기준으로, 시간 * 60 + 분 값을 적용해 정수 형태로 배열을 생성, 종료 시간은 + 10분 추가
        - 해당 배열을 시작 시간을 기준으로 오름차순 정렬
        - 종료 시간을 담는 우선순위 큐 생성
        - 모든 예약 시간을 순회
            - start : 시작, end : 종료 시간
            - 만약 방이 하나라도 있고, 기존 객실을 재사용 할 수 있다. -> !isEmpty() && peek() <= start 이면
                - poll()한 후 end 값 추가
        - 순회 이후, 우선순위 큐에 남아있는 크기 반환
*/

import java.util.*;

class Solution {

        public int solution(String[][] book_time) {
            int[][] times = new int[book_time.length][2];

            for (int i = 0; i < book_time.length; i++) {
                String[] split = book_time[i][0].split(":");
                int hour = Integer.parseInt(split[0]);
                int minute = Integer.parseInt(split[1]);
                times[i][0] = hour * 60 + minute;

                split = book_time[i][1].split(":");
                hour = Integer.parseInt(split[0]);
                minute = Integer.parseInt(split[1]);
                times[i][1] = hour * 60 + minute + 10;
            }

            Arrays.sort(times, (o1, o2) -> {
                return o1[0] - o2[0];
            });

            PriorityQueue<Integer> rooms = new PriorityQueue<>();

            for (int[] time : times) {
                int start = time[0];
                int end = time[1];

                if (!rooms.isEmpty() && rooms.peek() <= start) {
                    rooms.poll();
                }

                rooms.offer(end);
            }

            return rooms.size();
        }
    }

116번 점 찍기

/*
문제 분석
1. 정보
    - 진수는 x축과 y축이 직교하는 2차원 좌표 평면에 점을 찍으면서 놀고 있다.
    - 진수는 두 양의 정수 k, d 가 주어질 때 다음과 같이 점을 찍으려 한다.
        - 원점(0,0)으로부터 x축 방향으로 a*k, y축 방향으로 b*k만큼 떨어진 위치에 점을 찍는다.
        - 원점과 거리가 d를 넘는 위치에는 점을 찍지 않는다.

2. 목표
    - 정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return
3. 제약 조건
    - 1 <= k <= 1000000
    - 1 <= d <= 1000000

풀이
1. 아이디어
    - x,y에 점이 존재하려면
        - x^2 + y^2 <= d^2 이어야 함.
    - k씩 증가하므로,
        - (x + k)^2 + y^2 <= d^2 이어야 함.
        - 즉, y^2 <= d^2 - (x + k)^2 를 통해 x좌표마다 y의 최댓값을 구할 수 있음.
    - d^2은 최대 1조 이므로, long type 사용
    - x = 0 ; x <= d ; x += k 일동안
        - Y최대값 = Math.sqrt(d * d - x * x)
        - 결과값에 += (Y최대값 / k) + 1 (Y도 k의 배수이므로)
    - 결과값 return
*/

class Solution {
        public long solution(int k, int d) {
            long answer = 0;
            long dist = (long) d * d;

            for (int x = 0; x <= d; x += k) {
                long maxY = (long) Math.sqrt(dist - (long) x * x);
                answer += (maxY / k) + 1;
            }

            return answer;
        }
    }