Skip to main content

[level 4] 호텔 방 배정 - 64063

Intro

문제 링크

문제 설명​

호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 $k$개 있으며, 1번부터 $k$번까지 번호로 구분합니다. 처음에는 모든 방이 비어 있으며 다음 규칙에 따라 방을 배정합니다.

  1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
  2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
  3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
  4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

제한사항​

  • $k$는 1 이상 $10^12$ 이하인 자연수입니다.
  • room_number 배열의 크기는 1 이상 200,000 이하입니다.
  • room_number 배열 각 원소들의 값은 1 이상 $k$ 이하인 자연수입니다.

입출력 예시​

kroom_numberresult
10[1, 3, 4, 1, 3, 1][1, 3, 4, 2, 5, 6]

입출력 예 설명​

1번, 3번, 4번 고객은 원하는 방이 비어 있어 즉시 배정됩니다. 4번째 고객(1번 요청)은 1번이 차있으므로 2번을 배정받습니다. 5번째 고객(3번 요청)은 3, 4번이 차있으므로 5번을 배정받습니다. 6번째 고객(1번 요청)은 1, 2, 3, 4, 5번이 차있으므로 6번을 배정받습니다.

구현 코드​

import java.util.*;

class Solution {
    Map<Long, Long> map = new HashMap<>();

    public long[] solution(long k, long[] room_number) {
        int n = room_number.length;
        long[] answer = new long[n];

        for (int i = 0; i < n; i++) {
            answer[i] = findEmptyRoom(room_number[i]);
        }

        return answer;
    }

    private long findEmptyRoom(long room) {
        if (!map.containsKey(room)) {
            map.put(room, room + 1);
            return room;
        }

        long nextRoom = map.get(room);
        long emptyRoom = findEmptyRoom(nextRoom);
        map.put(room, emptyRoom);
        return emptyRoom;
    }
}

성능 요약​

메모리: 156 MB, 시간: 453.27 ms

채점결과​

정확성: 78.8

효율성: 21.2

합계: 100.0 / 100.0