📚 문제
"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
- 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
- 고객은 투숙하기 원하는 방 번호를 제출합니다.
- 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
- 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
예를 들어, 방이 총 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점으로 나왔습니다. 생각해봤을 때 for와 some으로 이중 반복문이기에 시간복잡도가 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에 현재 위치와 다음 위치를 저장해, 이미 등록되어 있는 방이면 그에 따른 부모 노드로 이동하므로써 시간을 단축 시킬 수 있었습니다.
📃 링크
