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

heumheum2·2020년 5월 7일
1

코딩테스트

목록 보기
4/5
post-thumbnail

📚 문제

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 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 함수를 완성해주세요.

📖 풀이

첫번 째 풀이

const solution = (k, room_number) => {
    const answer = [];
    for(let i = 0 ; i < room_number.length ; i++){
        if(answer.some(element => element === room_number[i])){
            if(k!==room_number[i]){
                room_number[i] += 1;
            }else{
                room_number[i] = 1;
            }
            i--;
        }else{
            answer.push(room_number[i]);
        }
    };
    return answer;
}


정확성과 효율성을 체크하는 테스트입니다. 정확성은 모두 정답이였지만 효율성은 0점으로 나왔습니다. 생각해봤을 때 forsome으로 이중 반복문이기에 시간복잡도가 O(N²)이 되는데, N²보다 작은 알고리즘으로 풀어야하는 문제인 것 같습니다.

두번 째 풀이

const solution = (k, room_number) => {
    const number = [...room_number];
    const answer = new Set([]);
    for(let i = 0 ; i < number.length ; i++){
        if(!answer.has(number[i])){
            answer.add(number[i]);
        }else{
            k===number[i] ? number[i] = 1 : number[i] ++;
            i--;
        }
    }
    return [...answer];
}

Set을 이용하여 시간복잡도를 O(N)으로 줄였습니다. 하지만 여전히 효율성 테스트는 실패라고 나오네요. O(log N)으로 줄여야 될 것 같습니다.

세번 째 풀이

const node = new Map();

const solution = (k, room_number) => {
    return room_number.map(number => find(k,number));
}

const find = (k, number) => {
    const getNumber = node.get(number);
    if(!getNumber){
        number === k ? node.set(number, 1) : node.set(number, number+1);
        return number;
    }
    return find(k, getNumber);
}


이번엔 재귀함수를 이용해서 풀어봤습니다. 시간이 더 줄었고, 효율성 테스트에 실패라고 나오네요! 조금 더 해봐야 할 것 같습니다. 검색해보니 **유니온 파인드(disjoint-set)**라는 키워드를 얻었습니다.

네번 째 풀이

const node = new Map();

const solution = (k, room_number) => {
    return room_number.map(number => find(number, k));
}

const find = (k, number) => {
    const getNumber = node.get(number);
    if(!getNumber) {
        number === k ? node.set(number, 1) : node.set(number, number+1);
        return number;
    } 
    node.set(number, find(k, number));
    return node.get(number);
}


find() 함수로 찾은 이후, Map 객체에 저장합니다. 이전 코드와 비교했을 때 node.set(number, find(k, number));를 추가했습니다.

위 코드를 추가함으로서 Map에 현재 위치와 다음 위치를 저장해, 이미 등록되어 있는 방이면 그에 따른 부모 노드로 이동하므로써 시간을 단축 시킬 수 있었습니다.

📃 링크

2019 카카오 개발자 겨울 인턴십 - 호텔 방 배정

profile
커피가 본체인 개발자 ☕️

0개의 댓글