🏨 카카오 2019 겨울 인턴십: 호텔 방 배정(Lv4)

📌 문제

스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

📌 제한사항

• k는 1 이상 1012 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.

📌 풀이

시뮬레이션으로 풀었더니 금방 해결할 수 있었다. 하지만 k의 범위가 너무 크기 때문에 효율성에서 전부 실패했다. 문제는 아래와 같이 해결 할 수 있었다.

1. 배정받은 방을 담는 Map이 필요하다. Map은 방 번호와 다음 방 번호를 담는다.
2. 고객이 원하는 방이 비어있는 경우, Map에 해당 방 번호와 다음 방 번호를 넣는다.
3. 고객이 원하는 방이 비어있지 않는 경우, 재귀를 통해 다음 방 번호를 찾는다.

📌 코드

import java.util.*;
class Solution {

    @Test
    void test() {
        assertThat(solution(10, new long[]{1,3,4,1,3,1})).isEqualTo(new long[]{1,3,4,2,5,6});
    }

    private Map<Long, Long> rooms = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        for (int i = 0; i < room_number.length; i++) {
            Long roomNumber;
            if (!rooms.containsKey(room_number[i])) {
                roomNumber = room_number[i];
            } else {
                roomNumber = findRoomNumber(room_number[i]);
            }
            answer[i] = roomNumber;
            rooms.put(roomNumber, roomNumber + 1);
        }
        return answer;
    }

    private Long findRoomNumber(Long roomNumber) {
        if (!rooms.containsKey(roomNumber)) return roomNumber;
        else {
            Long temp = findRoomNumber(rooms.get(roomNumber));
            rooms.put(roomNumber, temp);
            return temp;
        }
    }
}

프로그래머스

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