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

문제 설명

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

코딩테스트 연습 - 호텔 방 배정

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

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

 

입출력 예

k / room_number / result

10

[1,3,4,1,3,1]

[1,3,4,2,5,6]

 

입출력 예에 대한 설명

입출력 예 #1

문제의 예시와 같습니다.

 

첫 번째 ~ 세 번째 고객까지는 원하는 방이 비어 있으므로 즉시 배정받을 수 있습니다.

네 번째 고객의 경우 1번 방을 배정받기를 원했는데, 1번 방은 빈 방이 아니므로, 1번 보다 번호가 크고 비어 있는 방 중에서 가장 번호가 작은 방을 배정해야 합니다. 1번 보다 번호가 크면서 비어있는 방은 [2번, 5번, 6번...] 방이며, 이중 가장 번호가 작은 방은 2번 방입니다. 따라서 네 번째 고객은 2번 방을 배정받습니다. 마찬가지로 5, 6번째 고객은 각각 5번, 6번 방을 배정받게 됩니다.

 

---

풀이

- 일단 효율성 점수가 따로 있는 문제기 때문에 단순하게 생각하면 안 됨.

- map을 활용해 경로 단축을 하기로 함.

 

1. 효율성 3,4번 테스트 못한 코드

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        int len = room_number.length;
        long[] answer = new long[len];
        HashMap<Long, Long> map = new HashMap<>();

        for(int i=0; i<len; i++){
            long key = room_number[i];
            
            //방문 이력이 있다면 해당 위치에 +1, value만큼 인덱스 증가해서 안나올 때까지 가기
            while(map.containsKey(key)){
                long value = map.get(key);
                
                map.put(key, value+1);
                key += value;
            }
                 
            //해당 위치 방문이력이 없다면 1 추가 해주고 넘어가기
            map.put(key, (long)1);
            answer[i] = key;
        }
                  
        return answer;
    }
}

 

- map을 이용해 key는 방 번호, value는 해당 방 번호 요청 횟수로 생각해서 작성

 

1) 배정받고자 하는 방 번호가 map에 없다면 value에 1 넣어주고 answer 추가

2) 이미 배정받은 번호라면

- value값을 가져와 key에 그만큼 추가 : key += value;  (*key ~ key+value까지는 꽉 찼을 테니까)

- 또 해당 번호 value 값에 +1 해주기 (요청 횟수 증가)

 

3) 위에서 만든 새 키로 map에 키가 없을 때까지 탐색

- 즉, 배정받지 않은 key가 나올 때까지 탐색

 

- 나름 경로 단축을 생각해서 짠 건데, 효율성이 조금 부족했다. 

- 왜? 각 번호의 요청 횟수를 이용한 거라, 경로 단축이 덜 됨.

- 최종 미배정 번호(n)까지 도달하는 모든 경로의 value를 n+1로 갱신해주는 2번보단 느릴 수밖에 없음.

 

 

2. 재귀 함수를 이용해 경로 단축 (정확성, 효율성 둘 다 통과)

import java.util.*;

class Solution {
    HashMap<Long, Long> map;
    public long[] solution(long k, long[] room_number) {
        int len = room_number.length;
        long[] answer = new long[len];      
        map = new HashMap<>();

        for(int i=0; i<len; i++){
            answer[i] = find(room_number[i]);
        }
        return answer;
    }
    
    public long find(long r){
        if(!map.containsKey(r)){
            map.put(r, r+1);
            return r;
        }

        map.put(r, find(map.get(r))+1);  
        return map.get(r)-1;
    }
}

- 똑같이 map을 사용했지만 key는 방 번호, value는 연결된 다음 방 번호

 

1) 배정받고자 하는 방 번호가 map에 없다면 

- (방 번호, 방 번호+1) 값을 map에 추가 후, 방 번호 그대로 리턴

 

2) 이미 배정받은 번호라면

- 해당 방 번호의 value로 find() 함수 재호출 //재귀

- 타고 타고, 미배정 방 번호가 나올 때까지 찾아서 리턴

 

 

-> 쉽게 설명하면 key번 방을 요청했을 때 실제로 받을 수 있는 방 번호는 value

-> 하지만 value 방도 배정되었을 수 있으니 value를 key로 해서 재탐색 반복

 

 

 

자가 피드백

- 그래도 솔루션 안 보고 1번 생각해낸 건 좋았던 거 같음

- 전체 경로 업데이트 방법을 생각 못한 게 아쉬움 -> 재귀도 잘 생각해두자