[프로그래머스] 호텔 방 배정 (TypeScript로 풀기)

문제 설명

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

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 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 이상 1012 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

입출력 예

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

---

문제 풀이

방이 이미 사용되는지 확인하기 위하여 check라는 배열을 통하여 확인하기로 하였습니다. 사용 가능하다고 표현하기 위하여 모두 true로 채우는 반복문을 작성하였습니다. 그러고 room_number 배열을 순서대로 확인하는 for문을 이용하고 조건을 통하여 if(check[room_number[i]-1)로 요청한 방이 사용가능한지 검사하여 사용가능하다면 false로 변경하고 정답 배열에 추가합니다. 사용이 불가능하다면 반복문을 통하여 그 다음 방부터 확인하는 반복문을 통하여 가능한 방을 찾아갑니다.

function solution(k: number, room_number: number[]): number[] {
  let answer = [];
  let check: boolean[] = [];
  for (let i = 0; i < k; i++) {
    check.push(true);
  }
  for (let i = 0; i < room_number.length; i++) { //요청을 순서대로 확인하는 반복문
    if (check[room_number[i] - 1]) {
      check[room_number[i] - 1] = false;
      answer.push(room_number[i]);
    } else {
      for (let j = room_number[i]; j < k; j++) { //원하는 방이 없다면 그 다음 방부터 확인하는 반복문
        if (check[j]) {
          check[j] = false;
          answer.push(j + 1);
          break;
        }
      }
    }
  }
  return answer;
}

위의 방법을 사용하면 문제의 정답을 찾긴하지만 효율성에서 떨어져서 통과를 하지 못합니다.

어떻게 하면 효율적으로 찾을수 있을까 고민을 해보니 원하는 방이 안된다면 다음 방중에 어떠한 방이 가능한지 미리 기록을 해두고 같은방을 원하는 사람이 있으면 기록되어있는 다음 방에 배정을 해주는 방식을 선택하였습니다. 그러한 과정에서 Map객체를 이용하게 되었습니다. check라는 함수를 만들었습니다. 이 함수는 원하는 방이 비어있다면 roomList라는 객체에 채운 방의 번호를 키로하고 이 방을 또 찾는다면 가장 가까운 방을 값으로 객체에 저장을 합니다. 만약 이미 사용중이라면 roomList에서 키를 통하여 다음 방을  roomList.get(num)로 찾습니다.  찾은후에 이 방이 사용중인지 check를 재귀함수로 불러옵니다. 최종적으로 가능한 방을 반환하고 roomList에 저장하며 지정된 방을 반환하여 answer에 저장하는 방식으로 작성을 하니 효율성도 통과하였습니다.

function solution(k: number, room_number: number[]): number[] {
  const answer = [];
  const roomList = new Map();
  const check = (num: number) => {
    if (!roomList.get(num)) {
      roomList.set(num, num + 1);
      return num;
    }
    const nextRoom: number = check(roomList.get(num));
    roomList.set(num, nextRoom + 1);
    return nextRoom;
  };
  for (let i = 0; i < room_number.length; i++) {
    const num: number = check(room_number[i]);
    answer.push(num);
  }
  return answer;
}