[프로그래머스] 호텔 방 배정 (2019 카카오 겨울 인턴십) / JavaScript
알고리즘/프로그래머스

[프로그래머스] 호텔 방 배정 (2019 카카오 겨울 인턴십) / JavaScript

 

 

 

호텔 방 배정

 

https://programmers.co.kr/learn/courses/30/lessons/64063

 

코딩테스트 연습 - 호텔 방 배정

 

programmers.co.kr

 

 

 

 

풀이

 

function solution(k, room_number) {
  const rooms = new Map();

  const assignRooms = (num) => {
    if (!rooms.has(num)) {
      // 아직 배정받지 않은 방이라면, 다음 번호의 방을 담아준다.
      rooms.set(num, num + 1);
      return num;
    }
    // 이미 배정 받은 방이라면, 가리키고 있는 방이 배정 받았는지 확인한다.
    const nearestRoom = assignRooms(rooms.get(num));
    rooms.set(num, nearestRoom + 1);
    return nearestRoom;
  };

  return room_number.map(assignRooms);
}

 

k 는 전체 방 개수

room_number는 고객들이 원하는 방 번호가 들어있는 배열

 

방을 배정하는 규칙은 다음과 같다.

𝟙. 신청 순으로 방을 배정한다.
𝟚. 각자 원하는 방 번호를 제출하면 해당 방이 비어있는지 살펴본다.
𝟛. 원하는 방이 비어있다면, 해당 방을 배정한다
𝟜. 만약 원하는 방이 이미 배정된 상태라면, 비어있는 방 중 원하는 방보다 숫자가 크면서 가장 가까운 방으로 배정한다.

 

유니온 파인드(Union Find)를 활용하여 풀었다.

방의 크기(k)는 1부터 10^12 까지로 효율성을 보는 문제이기 때문에 일반 배열이나 객체 대신 Map을 사용했다.

 

rooms 는 배정된 방들이 들어있다. 따라서 방이 배정된 여부는 room 에 존재하는지로 파악할 수 있다.

방 배정을 보다 효율적으로 하기 위해서 방이 배정되는 것과 동시에 대체할 방의 번호를 value값으로 넣어준다.

rooms 에 들어가는 원소 key 값은 방 번호, value는 𝟜번을 만족하는 대체 방의 번호가 들어가게 된다.

 

 

 

 

 

 

예제를 통해서 간단하게 설명하자면, 아직 빈 맵객체인 rooms와 room_number = [1,3,4,1,3,2]가 있다. 그림으로는 아래와 같이 나타내었다.

 

 

 

room_number를 차례대로 탐색하면서 방을 배정해준다.

 

첫번째 고객이 원하는 방은 1번이고 아직 방 1번은 비어있으므로, 첫번째 고객에게 방 1번을 배정해준다.

배정된 방은 rooms에 넣어준다. key값으로 방 번호인 1을, value로는 숫자가 크면서 가장 가까운 방인 2번을 넣어준다.

동일한 로직으로 두번째 고객에게는 3번 방을, 세번째 고객에게는 4번 방을 배정한다.

 

 

 

이제 4번째 고객에게 방 배정을 해보자.

4번째 고객은 방 1번을 배정받기를 원하지만, 1번은 이미 배정되어있다.

이때 방 1번의 value인 2번 방이 비어있는지 확인한다. 2번 방은 비어있으므로, 4번째 고객에게 방 2번을 배정해준 후 rooms에 key값으로 2, value로는 다음 가까운 방인 3번을 넣어준다.

 

주의해야할 점은 배정됐는지 확인했던 모든 방의 value를 변경해주어야 한다는 것이다. 여기에서는 1번 방이 비어있는지를 확인했기 때문에 1번 방의 value를 3으로 바꿔준다.

 

 

 

 

5번째 고객은 3번 방을 원한다. 안타깝게도 rooms에는 이미 3번 방이 들어있다.

3번 방의 value인 4번 방을 확인해보자. 4번 방도 이미 배정된 상태이다.

4번 방의 value인 5번 방을 확인한다.

5번 방은 아직 배정되기 전이다. rooms에 key값으로 5, value로는 다음 가까운 방인 6번을 넣어준다. 빈 방인지 확인했던 3, 4번 방의 value도 6번으로 변경해준다.

 

 

 

마지막 6번째 고객이 남았다.

6번째 고객이 원하는 2번 방이 rooms에 존재하는지 확인해보자.

2번이 rooms에 존재하므로, value인 3번 방을 확인해준다. 3번방도 이미 존재한다.

3번 방의 value인 6번 방을 확인한다.

6번 방은 아직 존재하지 않으므로, rooms에 6을 추가해준다. value는 7이 된다.

마무리로 빈 방인지 확인했던 2, 3번 방의 value도 바꿔준다.

 

 

 

 

 

 

 

 

    티스토리툴바