[프로그래머스] 2019 카카오 겨울인턴. 호텔 방 배정 (Java)

Problem

• 문제 링크

총 방의 갯수 k 와 고객들이 선택한 방이 주어질 때 각 방별로 배정된 사람들의 목록을 return 하는 문제입니다.

방은 고객들이 선택한 순서대로 정해집니다.

A 고객이 선택한 방을 이미 B 고객이 선택했다면 A 고객은 다음 방을 배정받습니다.

A 고객이 선택한 방번호보다 크고 아무도 선택하지 않은 가장 작은 방번호가 다음 방입니다.

Solution

정확성 뿐만 아니라 효율성까지 고려해야 하는 문제입니다.

단순하게 풀이한다면 Set 자료구조에 선택된 방들을 담아두고 중복된 방을 선택한 경우 +1 하며 전체 스캔하는 것으로 정확성은 통과할 수 있다.

하지만 k 가 최대 10^12 이기 때문에 O(n)으로 매번 검색을 해버리면 효율성을 하나도 통과할 수 없습니다.

다음 방을 선택하는 과정에서 O(n) 으로 스캔하는 건 어쩔수가 없습니다.

그렇다면 한번 선택한 방은 다음번에 선택할 때 스캔을 최소 로 한다면 정확성을 통과할 수 있습니다.

접근법은 우선 HashMap 을 선언하여 <방 번호 : 다음 방 번호> 이렇게 저장해두는 겁니다.

고객이 방을 선택했을 때 map.containsKey() 로 다음 방을 바로 찾을 수가 있죠.

다음으로 할 일은 다음 방을 갱신해주는 겁니다.

예를 들어 방이 6 번까지 있고 [1, 2, 3, 4] 는 이미 선택되었다고 가정합니다.

다음 고객이 1 을 선택하였을 때 5 번 방이 비어있는 걸 알기 위해 1 -> 2 -> 3 -> 4 -> 5 순서대로 가야 하지만

다음 방을 미리 저장해둔다면 1 -> 5 로 바로 스캔할 수 있습니다.

그리고 1 번을 갱신하는 김에 2, 3, 4 방도 똑같이 다음 방이 5 니까 갱신해줍니다.

이것을 재귀로 구현한 게 long findEmptyRoom(long room) 함수입니다.

Java Code

import java.util.*;

class Solution {
    Map<Long, Long> map = new HashMap<>();

    public long[] solution(long k, long[] room_number) {
        int n = room_number.length;
        long[] answer = new long[n];

        for (int i = 0; i < n; i++) {
            answer[i] = findEmptyRoom(room_number[i]);
        }

        return answer;
    }
    
    private long findEmptyRoom(long room) {
        if (!map.containsKey(room)) {
            map.put(room, room + 1);
            return room;
        }
        
        long nextRoom = map.get(room);
        long emptyRoom = findEmptyRoom(nextRoom);
        map.put(room, emptyRoom);
        return emptyRoom;
    }
}