[프로그래머스 / Level4] 호텔 방 배정 (Java)

문제 보기

사용한 것

• 방의 개수가 최대 10의 12승이기 때문에 배열 대신 해시테이블로 구현한 union-find

풀이 방법

• find()로 현재 방에서 크거나 같은 최대한 가까운 방을 찾는다.
• 찾은 방을 배정하면 해당 방번호 + 1과 union()한다.

코드

package test132;
// 해시테이블/프로그래머스/Level4/호텔 방 배정

import java.util.HashMap;
import java.util.Map;

class Solution {

    private final Map<Long, Long> map = new HashMap<>();

    public long[] solution(long k, long[] room_number) {
        long[] assignedRooms = new long[room_number.length];
        for (int i = 0; i < room_number.length; i++) {
            assignRoom(assignedRooms, i, room_number[i]);
        }
        return assignedRooms;
    }

    private void assignRoom(long[] assignedRooms, int customerIdx, long want) {
        long assignedRoom = find(want);
        union(assignedRoom, assignedRoom + 1);
        assignedRooms[customerIdx] = assignedRoom;
    }

    private void union(long num1, long num2) {
        num1 = find(num1);
        num2 = find(num2);
        if (num1 != num2) {
            map.put(num1, num2);
        }
    }

    private long find(long num) {
        if (!map.containsKey(num)) {
            return num;
        }
        long nextNum = find(map.get(num));
        map.put(num, nextNum);
        return nextNum;
    }
}