[Programmers] 호텔 방 배정

[2019 카카오 겨울 인턴십] 호텔 방 배정

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

 

 

Solution

• 처음에 연결리스트를 사용해서 room이 이미 선택됐을 경우 room+1  부터 순회하면서 방을 탐색하는 방식으로 구현했었는데 O(N)의 시간복잡도로는 해당 문제의 효율성 테스트를 통과할 수 없었다.
• 이후 다른 사람의 풀이에서 HashMap을 사용해 다음 방을 탐색하는 횟수를 최소로 하는 탐색 방법을 볼 수 있었다.
• map.put(선택된 방, 다음 방)으로 탐색의 시작점을 기록하는 것이다.

 

1. room_number 배열의 모든 원소에 대해 findEmptyRoom(int room) 함수를 호출

2. map에 room이 없는 경우는 아직 선택되지 않은 방을 뜻하기 때문에 map.put(room, room+1) 후 room을 리턴한다.

3. map에 room이 존재하는 경우 map에 미리 저장한 room의 다음 방에 대하여 빈방을 찾을 때 까지findEmptyRoom(nextRoom)를 재귀적으로 호출한다.

4. 그리고 빈 방을 찾았을 경우에 마지막으로 찾은 빈방을 처음에 호출했던 room의 다음 방으로 갱신해준다.

 

 

 

 

소스코드

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
 
 
public class Main {
    static Map<Long, Long> map = new HashMap<>();
 
    public static long[] solution(long k, long[] room_number) {
        int n = room_number.length;
        long[] answer = new long[n];
 
        for (int i = 0; i < n; i++) {
            System.out.println("i = " + i);
            answer[i] = findEmptyRoom(room_number[i]);        
        }
 
        return answer;
    }
    
    private static long findEmptyRoom(long room) {
        if (!map.containsKey(room)) {    // 1. 내가 선택한 방이 map에 없음 => 선택할 수 있음
            map.put(room, room + 1);    // 1-1. 이미 선택된 방임을 기록하기 위해 다음 번호의 방과 함께 put       
            return room;    // 1-2. room 그대로 return
        }
        
        long nextRoom = map.get(room);    // 2. 내가 원하는 방이 map에 있음 => 다음 방 선택해야함
        long emptyRoom = findEmptyRoom(nextRoom);    // 2-1. 다음 방에 대해 선택 시도 => 선택 가능한 emptyRoom을 찾을 때 까지 반복됨
        map.put(room, emptyRoom);    // 2-2. 다음 방 갱신 작업     
        return emptyRoom;
    }
 
    public static void main(String[] args) throws IOException {
        solution(10, new long[] {1,2,3,4,1,2});
    }
 
    static int stoi(String s) {
        return Integer.valueOf(s);
    }
 
}
 

 

 

참고 자료

https://bcp0109.tistory.com/entry/Kakao-2019-Internship-Winter-%ED%98%B8%ED%85%94-%EB%B0%A9-%EB%B0%B0%EC%A0%95-Java