[JS] - 카카오 인턴 호텔방 배정(유니온파인드)

풀이

• 못풀었음

• Union - Find 알고리즘 + 해쉬맵 사용

• 크루스칼 알고리즘에 사용됨

Union - Find 기본 소스코드

int root[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
    parent[i] = i;
/* find(x): 재귀 이용 */
int find(int x) {
    // 루트 노드는 부모 노드 번호로 자기 자신을 가진다.
    if (root[x] == x) {
        return x;
    } else {
        // 각 노드의 부모 노드를 찾아 올라간다.
        return find(root[x]);
    }
}
/* union(x, y) */
void union(int x, int y){
    // 각 원소가 속한 트리의 루트 노드를 찾는다.
    x = find(x);
    y = find(y);
    root[y] = x;
}

문제

문제 링크

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

소스코드

const solution = (k, roomNumbers) => {
  const used = new Map(); 
  const answer = roomNumbers.map((number) => findRoom(number, used)); 
  for(let x of used){
      //console.log(x);
  } 
  return answer
}; 
function findRoom(room, used) { 
     // 방이 비어있는경우 
  if (used.get(room) == undefined) {
    used.set(room, room + 1);
    return room;
  }
  let next = findRoom(used.get(room), used);
  used.set(room, next + 1);
  return next;
}