[Algorithm] 호텔 방 배정

📋 문제

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

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 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] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.
•  

입출력 예

10

[1,3,4,1,3,1]

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

 

✏️ 풀이

이전에 union&find 문제를 풀었던 기억이 나서 비슷한 방법으로 풀어야겠다고 생각했다.

 

find라는 함수를 작성했다. find는 자료구조에 해당 수를 기준으로 사용할 수 있는 가장 작은 수(배정되어 있지 않다면 해당 수 / 이미 배정되어 있다면 1씩 증가시키며 다음 수)를 반환한다.

 

k의 크기가 10^12이기 때문에 배열을 생성하기에는 어려울 것 같았기 때문에 객체를 사용하였다. 만약 hash라는 객체에 원하는 방 번호를 키로 가지는 값이 없다면 배정할 수 있는 방이라는 뜻이므로 방 번호를 반환하고 hash 객체에는 방 번호를 key로 방 번호 + 1을 값으로 저장했다. 방 번호 + 1을 할당하는 이유는 이후에 같은 수의 방을 원하는 경우 객체에서 참조하여 반환하주기 위함이다. hash 객체에서 을 인덱스로 확인했을 때 존재한다면 이미 배정된 room이기 때문에 hash[room]을 인자로 find 함수를 재귀호출하고 이를 hash[room]에 저장했다. 

 

만약 1번방부터 3번방까지 모두 배정이 되어있을때 1번 방을 원하는 경우를 예로 들어보자. {1: 2, 2: 3, 3: 4}로 hash에 저장되어 있을텐데 find 함수를 호출하면 이미 1번방이 배정되어 있기 때문에 find(hash[1])을 재귀호출하고 이후로도 3번방까지 배정되어 있으므로  find(hash[2]), find(hash[3])이 호출되어 hash[4]에 5를 할당하고 5를 반환한다. 이때 함수 컨텍스트가 하나씩 종료되면서 마지막에 반환값을 hash[room]에 할당해 최신화를 해준다. 5가 계속 반환값으로 오기 때문에 {1: 5, 2: 5, 3: 5, 4:5}로 최신화되고 이후에 이미 배정된 다른 방을 원할 때 5까지 보다 빠르게 도달할 수 있다.

 

문제는 이렇게 코드를 작성했을 때 정확성테스트는 모든 테스트케이스를 통과하지만 효율성 테스트하나를 통과하지 못했다. 코드의 개선사항은 도저히 없을 것 같았고 재귀호출이 아닌 while문을 사용했음에도 결과는 같았다. 혹시 객체를 사용해서 인덱싱하는 것보다 효율적인 방법이 있을까라는 것이었고 대안으로는 Map객체가 있었다. 기존의 객체를 사용했던 코드를 map의 메서드 set, get, has를 사용해서 제출하니 통과가 됬다.

 

map보다는 객체가 더 빠를 것이라고 생각했는데 걸린 시간의 차이를 보니 몇 배의 차이가 났다. 객체와 map의 차이점을 정리해주신 분의 포스팅을 봤는데 다음과 같았다.

 

	Map	Object
key Types	Map은 어떠한 값도 key로 가질 수 있다.	Object의 key는 String 또는 Symbol이어야 한다.
key Order	Map은 삽입한 순서대로 key가 정렬되어 있다. Map을 iterate할 경우 삽입된 순서대로 나온다.	Object의 key들은 현재는 순서대로 정렬되기는 하지만, 해당 순서들은 항상 보장되는 것은 아니며 Object property 순서에 의존하지 않는 것이 좋다.
Iteration	Map 은 이터러블하며 direct하게 iterate 할 수 있다.	Object는 iteration 프로토콜을 사용하지 않으며 따라서 direct 하게 iterate를 할 수 없다. (Object.keys 나 Object.entries 또는 for..in 구문을 사용하여야 한다)
performance	빈번한 key-value pair의 삽입과 삭제시 더 높은 performance를 가진다. get에서 object에 비해 performance가 느리다는 이야기가 있다.	key-value pair의 빈번한 추가 및 삭제에 대한 최적화가 되어있지 않다.
Serialization and parsing	No native support for serialization or parsing	JSON.stringify() 및 JSON.parse()를 지원한다.

출처 - https://velog.io/@namda-on/JavaScript-Map-%EA%B3%BC-Object-%EC%9D%98-%EC%B0%A8%EC%9D%B4

 

Map이 빈번한 key-value pair의 삽입과 삭제시 더 높은 performance를 가진다고 한다!! Map 자료구조 애용해야겠당

 

⌨️ 코드

function solution(k, room_number) {
  var answer = [];

  const hash = new Map();
  const find = room => {
    if (!hash.has(room)) {
      hash.set(room, room + 1);
      return room;
    } else {
      const findRoom = find(hash.get(room));
      hash.set(room, findRoom);
      return findRoom;
    }
  };

  for (const number of room_number) {
    const room = find(number);
    answer.push(room);
  }

  return answer;
}