프로그래머스 [Lv. 4] 호텔 방 배정 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(k, room_number) {
    const answer = [];
    let visited = new Map();
    for (const rn of room_number) {
        if (!visited.has(rn)) {
            visited.set(rn, rn + 1);
            answer.push(rn);
            continue;
        };
        let tmp = rn;
        const stack = [rn];
        while (visited.has(tmp)) {
            tmp = visited.get(tmp);
            stack.push(tmp);
        }
        visited.set(tmp, tmp + 1);
        answer.push(tmp);
        for (const st of stack) {
            visited.set(st, tmp + 1);  
        };
    }
    return answer;
}

풀이 방법

1. Map 객체를 생성한다.
2. Map.prototype.has()를 사용하여 방이 이미 예약 되었는지 확인한다.
   1. has(key) 
   2. 주어진 키에 연관된 값이 Map 객체에 존재하는지 여부를 불리언 값으로 반환합니다.
3. 방이 없을 경우 Map.prototype.set()를 사용하여 값을 추가한다.
   1. set(key, value) 
   2. Map객체에서 전달된 키의 값을 설정합니다. Map객체를 반환합니다.
   3. answer에 rn값을 push 한다.
4. 방이 있을 경우 Map.prototype.get()을 사용하여 값을 추출한다.
   1. get(key)
   2. 주어진 키에 해당하는 값을 반환하거나 값이 없다면 undefined을 반환합니다.
5. 순회하며 나온 tmp 값을 stack에 넣는다.
   1. 예약이 되지 않은 방을 찾은 경우 방에 tmp+1값을 넣는다.
   2. answer에 tmp값을 push 하고 stack에 값들을 tmp+1로 바꾼다.
6. stack을 이용하는 이유
   1. [5, 5, 5, 5, 5, ... , 5] 형태의 배열이 나왔을 때 5번 방에 방을 배정하고 visited를 tmp+1로만 바꿀 경우 문제가 발생한다.
      1. 5번에 방배정하고 6번 방을 배정할 수 있게 도와주지만 5번에서 계속해서 6번 방을 요구하고 6번은 7번 방을 7번은 8번 ... n번 방까지 순회하는 문제가 발생하게 된다.
      2. 따라서 미리 5번 방을 6, 7, 8 ... n번 방으로 업데이트 하게 되면 시간 복잡도를 줄일 수 있게 된다.

느낀점

• Map과 Object에 대한 차이는 다음 사이트를 참고하는 것이 좋다.
  • https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map

Map - JavaScript | MDN