프로그래머스_호텔 방 배정_64063

문제 링크

조건

• K - 전체 방 개수(1 ~ 10^12)
• room_number - 고객이 원하는 방 번호 : length 1~200,000 / 범위 1 ~ K

접근 방법

• Union Set으로 이미 배정된 방들 중 붙어있는 방 끼리 Union 처리
• K의 범위가 long type이기 때문에 방마다의 parent 정보 를 배열로 저장할 수 X => HashMap 사용

  주의 : 이미 배정한 방일 경우 아직 배정하지 않은 방 중 가장 작은 방 번호를 탐색해야 함 => findSet => 여기서 기존 배정한 방들의 parent 정보를 계속 갱신해줘야 이후의 findSet 탐색이 빨라짐

솔루션

import java.util.*;
/*
    union set!!!
    if - hashmap에 고객이 요청한 방 번호가 있다면 
        => 이미 누군가에게 배정된 번호
        : findset으로 최상위 parent 찾은 후 map에 없으면 그 방 번호 배정 후 hashmap에 추가
    else => 배정된 적 없는 번호
        : 그 방 번호 배정 후 hashmap에 추가
*/
class Solution {
    HashMap<Long, Long> rooms = new HashMap<>();
    long[] answer;
    public long[] solution(long k, long[] room_number) {
        answer = new long[room_number.length];

        for(int i = 0, size = room_number.length; i < size; i++){
            long n = room_number[i];//요청한 방 번호
            if(rooms.containsKey(n)){//이미 배정한 방이라면
                n = findSet(n);//아직 배정하지 않은 방 중 가장 작은 방 번호 탐색
            }
            answer[i] = n;//최종 번호로 방 배정
            rooms.put(n, n+1);//새로 배정한 방은 다음 방 번호와 묶어서 hashmap에 저장
        }

        return answer;
    }

    public long findSet(long r){
        long p = rooms.get(r);
        if(!rooms.containsKey(p)) return p;//아직 배정하지 않은 방을 찾으면 그 방 번호 return

        p = findSet(p);
        rooms.put(r, p);
        return p;
    }
}