호텔 방 배정

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

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

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호	배정된 방 번호
1	1
3	3
4	4
1	2
3	5
1	6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 > 완성해주세요.

[제한사항]

• k는 1 이상 10^12 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

문제 풀이

1. 해당 번호로 예약할 때, 해당 번호의 방이 예약가능한지 Map 객체를 이용해서 확인한다.
   1. 해당 번호의 방이 없어 예약할 수 있는 경우
      1. 예약하고 해당 번호에 다음 방 번호를 저장한다.
   2. 해당 번호의 방이 있어 예약할 수 없는 경우
      1. 재귀적으로 해당 번호로 저장할 수 있는 방을 찾는다.
      2. 찾은 방의 +1로 모든 해당 번호가 거쳐온 방들을 바꿔준다.

주의해야할 점

Object는 Map보다 삽입 / 삭제가 오래걸려 Map을 이용해야한다.

소스코드

function solution(k, room_number) {
  let answer = [];
  let map = new Map();

  room_number.forEach(num => {
    if (!map.get(num)) {
      map.set(num, num + 1);
      answer.push(num);
      return;
    }
    const index = find(map, num);
    map.set(index, index + 1);
    answer.push(index);
  });
  return answer;
}

function find(map, num) {
  if (!map.get(num)) return num;
  const next = find(map, map.get(num));
  map.set(num, next + 1);
  return next;
}