[JAVA] 호텔 방 배정 (2019 카카오 개발자 겨울 인턴십) - LEVEL4

문제 : 호텔 방 배정

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

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

---

[입출력 예]

kroom_numberresult

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번 방을 배정받게 됩니다.

---

아이디어 및 알고리즘

• 이문제는 HashMap을 이용하여 key값으로 방번호를 Value값으로 같은 방번호가 들어왔을때 어느 방으로 선택되어야할지를 알려주는 값입니다. 이 알고리즘을 통해 방배정을 겹치지 않고 배정할 수 있게됩니다.
• 이번 문제에서는 정확성 뿐만 아니라 효율성 까지 통과해야하기 때문에 일반적인 풀이에서는 시간초과가 나기 쉽기때문에 그 부분을 신경쓰면서 해야 합니다. 그래서 경로압축에 신경을 쓰셔서 풀어야 합니다.
• 또 하나의 알고리즘으로는 Union-Find 알고리즘으로 Disjoint-set이라 하는 그래프 알고리즘을 사용하는 방법입니다. 이 방법은 저도 한번도 써보진 않았던 거라 나중에 시간이 되면 할 예정입니다.

소스 코드

import java.util.HashMap;
class Solution {
    static HashMap<Long, Long> hm;
    public long[] solution(long k, long[] room_number) {
        int room_count=room_number.length;
        long[] answer = new long[room_count];
        hm = new HashMap<Long, Long>();
 
        for(int i=0;i<room_count;i++) {
 
            if(!hm.containsKey(room_number[i])) { 
                answer[i]=room_number[i];
                hm.put(room_number[i],room_number[i]+1);    
            }
            else {
                long room_value = findValue(hm.get(room_number[i])); 
                answer[i]= room_value;
            }           
        }      
        return answer;
    }
        public static long findValue(long key) {
        if(!hm.containsKey(key)) {
            hm.put(key, key+1);
            return key;
        }
        hm.put(key, findValue(hm.get(key)));
        return hm.get(key);
    }
 
}

코드 설명

문제를 풀기에는 어렵지 않았지만 경로압축에 대해서 오래걸렸습니다. findValue함수를 통해 key가 존재했을때 재귀함수로 돌리면서

방문할때마다 key값에 대한 value값을 계속 업데이트 해주면서 다음 방을 return 하는 방식을 사용했습니다. 

다른 방법으로 Arraylist를 이용해 한번에 value값을 업데이트 해주는 방법도 해봤지만 시간초과가 나서 구글링을 하여 참고하면서 풀게 되었습니다.

 

코드 결과

후일담

처음 문제를 봤을땐 어렵지 않았지만 풀고 나서 계속 시간초과가 나는 문제가 많았다 그래서 자꾸 고치고 최대한 시간을 줄여보려고 노력했던 문제이다. 와... 아직 알고리즘 마스터가 되기까지 험난한 여정이 될거 같던 문제였다. 매번 풀면서 더 노력해야만 한다는 생각 밖에 들지 않았다. 오늘 비가 왜이리 많이 오는지 코딩하기 좋은 날씨다😊😊

 

문제 링크

https://programmers.co.kr/learn/challenges?tab=all_challenges