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

import java.util.*;

class Solution {
    Map<Long,Long> assignedRoom = 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++){
            if (!assignedRoom.containsKey(room_number[i])) {
                answer[i] = room_number[i];
				assignedRoom.put(room_number[i],room_number[i]+1);
            } else {
                Long replacedRoom =findRoom(room_number[i]);
                answer[i] = replacedRoom;
            }
        }
        return answer;
    }
    
    private long findRoom(long room_number) {
        List<Long> eveRoom = new LinkedList<>();
        while(assignedRoom.containsKey(room_number)){
            eveRoom.add(room_number);
            room_number = assignedRoom.get(room_number);
        }
        assignedRoom.put(room_number,room_number+1);
        updateNextRoom(eveRoom,room_number+1);
        return room_number;
    } 
    
    private void updateNextRoom(List<Long> eveRoom,long nextRoom){
        for(int i=0; i<eveRoom.size(); i++){
            assignedRoom.put(eveRoom.get(i),nextRoom);
        }
    }
}

1. k값이 매우 클 수 있으므로, 배열을 선언하여 조회하는 행위는 시간초과가 날 것이 뻔해서 map을 이용하여 풀었다.

2. 원하는 방 번호가 아직 배정되지 않았을경우 바로 배정해주고,  map에 <배정받은방,다음에 탐색할 방>의 형식으로 값을 저장한다.

이때, 방 번호가 없어 바로 배정되었으므로 이후의 가장 낮은 숫자의 방인 배정받은방+1 값을 다음에 탐색할 방으로 지정한다.

3. 원하는 방 번호가 이미 배정되었을 경우, 다음에 탐색할 방이 배정되어있지 않을때까지 탐색하여 가장 작은 방번호를 구해내고 그 방을 배정해준다. 

4. 이때, 배정된 방이 되기전의 방들은 모두 배정된 상태였으므로,

탐색 시간을 줄이기 위해서 전에 탐색했던 모든 방들의 다음 탐색할 방을 3번에서 배정한 방의 다음방으로 만든다. 

※ 처음에는 updateNextRoom에서 모든 방들을 탐색하니까 효율성 테스트를 통과하지 못해서

findRoom에서 거쳐왔던 room_number들을 리스트에 담아서 넘겨주어

해당 room들만 업데이트 시켜주니까 효율성 테스트까지 통과하였다.