[프로그래머스] 호텔 방 배정

문제

---

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

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 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] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

 

 

 

풀이

---

HashMSet을 이용해서 풀면 쉽게 풀수 있지만 효율성에서 시간초과가 난다.

 

그래서 생각한게 HashMap을 이용해서 가장 마지막 빈방에 저장된 값을 가지고 있으면 좋겠다.

그리고 그사이에 모든 연속 된  방들은 가장 나중에 저장된 빈방의 번호를 가지고 있으면 좋겠다.

 

이 두가지 방식을 구현했다.

 

반복문을 이용해서 풀려하다보니 시간초과가 났다.

이유는 해당 방번호와 마지막에 저장된 방번호의 사이의 모든 방의 가장 마지막수를  바꿔주다보니 생긴 시간초과인것 같았다.

 

지나쳐간 방들의 값들만이라도 바꿔주는 것이 좋겠다. 재귀를 이용해서 지나간 방들의 값만 최신화 해준다.

 

<빈방 찾는 코드>

    static long findEmptyRoom(long roomNumber){
        
        if(!room.containsKey(roomNumber)){
            
            room.put(roomNumber, roomNumber + 1);
            return roomNuber;
        }
        
        long emptyRoomNumber = findEmptyRoom(room.get(roomNumber));
        room.put(roomNumber, emptyRoomNumber + 1);
        return emptyRoomNumber;
        
    }

위와 같이 재귀를 돌면서 해당 방의 위치가 비어있으면 값을 넣어준다.

여기서 +1 을 하는 이유는 이미 이방은 꽉찼기 때문에 다음에 같은 값이 들어오면 시간을 한번더 줄여주기 위함이다.

 

이렇게 비어있지 않지만 비어있다고 저장된 모든 방들의 값들을 최신화 시켜준다.

 

<전체코드>

import java.util.*;

class Solution {
    
    static HashMap<Long, Long> room;
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];        
        
        room = new HashMap<Long, Long>();
        
        for(int i = 0 ; i < room_number.length ; i++){
            
            answer[i] = findEmptyRoom(room_number[i]);
        }
        
        return answer;
    }
    
    
    static long findEmptyRoom(long roomNumber){
        
        if(!room.containsKey(roomNumber)){
            
            room.put(roomNumber, roomNumber + 1);
            return roomNuber;
        }
        
        long emptyRoomNumber = findEmptyRoom(room.get(roomNumber));
        room.put(roomNumber, emptyRoomNumber + 1);
        return emptyRoomNumber;
        
    }
}

 

레벨 4문제였지만 특별한 알고리즘적인 이론이 들어가는 것이 아니기 때문에, 경로를 압축할 방식만 잘 생각해내면, 다들 쉽게 풀 수 있을 것으로 생각된다.