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

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

코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    static public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];

        // key : 방 번호, value : 현재 방보다 크면서 비어있는 방
        // value는 초기 상태로 현재 방 번호보다 1 큰 숫자를 가진다.
        Map<Long, Long> rooms = new HashMap<>();

        for (int i = 0; i < room_number.length; i++) {
            // 배정되지 않은 빈 방이라면
            if (!rooms.containsKey(room_number[i])) {
                // 그대로 원하는 방 배정
                answer[i] = room_number[i];

                // 방 배정됐으면 hash 데이터 추가
                rooms.put(room_number[i], room_number[i] + 1);
            }
            // 빈 방이 아니라면 다음 방을 탐색한다.
            else {
                List<Long> updateRoomList = new ArrayList<>();
                updateRoomList.add(room_number[i]);

                long nextRoom = rooms.get(room_number[i]);

                while (true) {
                    // 할당되지 않은 빈 방임
                    if (!rooms.containsKey(nextRoom)) {
                        answer[i] = nextRoom;
                        rooms.put(nextRoom, nextRoom + 1);
                        break;
                    }
                    // 이미 할당된 방일 경우 다음 방을 갱신하기 위해 리스트에 저장해둔다.
                    else {
                        updateRoomList.add(nextRoom);
                        nextRoom = rooms.get(nextRoom);
                    }
                }

                // 확인했던 방들의 다음 방 번호 갱신
                for (Long aLong : updateRoomList) {
                    rooms.put(aLong, nextRoom + 1);
                }
            }
        }

        return answer;
    }
}

풀이

전체 방 개수가 10^12개 이므로 배열을 이용해 모든 방을 나타낼 경우 메모리가 부족하게 된다. 때문에 HashMap 등의 자료구조를 이용해 필요한 만큼 노드를 생성해 메모리를 절약할 수 있다.

먼저 고객에게 배정할 방이 빈 방이면 즉시 배정한다. 이 때, Map 변수에 key는 배정된 방 번호, value는 현재 방 번호에 1을 더한 값을 저장한다.

만약 고객에게 배정할 방이 빈 방이 아니면 다음과 같이 배정할 빈 방을 탐색한다.

• 현재 노드의 방이 빈 방이 아니면 빈 방이 나올 때까지 부모 노드를 계속 방문한다.
• 빈 방이 나오면 고객에게 배정하고, 배정된 방 번호를 노드(key)로 만든 후, 부모 노드(value)는 배정된 방 번호에 1을 더해준 값을 저장한다.
• 빈 방이 나오기 전까지 방문한 노드들의 부모 노드 또한 고객에게 배정한 방 번호에 1을 더한 값으로 수정한다.

참고

• 2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설