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

문제

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

프로그래머스

 

소스코드

import java.util.Arrays;
import java.util.HashMap;

class Solution {

    HashMap<Long, Long> rooms;

    public long[] solution(long k, long[] room_number) {

        rooms = new HashMap<>();

        return Arrays.stream(room_number)
                        .map(this::findRoom)
                        .toArray();
    }

    public long findRoom(long num) {

        if(!rooms.containsKey(num)) {
            rooms.put(num, rooms.getOrDefault(num+1, num+1));
            return num;
        }

        long next = findRoom(rooms.get(num));

        rooms.put(num, next);
        return next;
    }

}

 

회고

 문제를 보고 Union-Find가 떠올랐다. 입력값이 크기 때문에 배열 대신 해시맵으로 <예약 된 방 번호 : 다음 방 번호>의 자료구조를 사용했고, 다음 방 번호를 찾을 때 재귀를 통해 계속해서 맵을 업데이트 해주었다.