(프로그래머스) 호텔 방 배정

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

 

🐢 설명

문제는 매우 직관적이다.

 

원하는 방번호를 요청하고 없으면 요청한 방 번호보다 큰 번호 중 가능한 첫번째 방번호를 반환하고, 있으면 바로 반환하면 되는 문제이다.

그런데 요청 가능한 방번호의 범위가 무려 10^12승으로 1조이다. 전세계 방을 다합쳐도 안될것같은 방의 개수이지만 요구사항을 잘 지켜보자.

 

문제를 풀 수 있는 힌트는 방 번호는 최대 1조까지 있지만, 요청하는 방 번호의 개수는 20만개로 제한적이다.

 

따라서 일반적인 배열 대신 Map 자료구조를 이용한 유니온-파인드를 통해 요구 방마다 (자신의 방 번호 - 부모 방 번호) 구조를 갖도록 하면 메모리 걱정없이 풀 수 있다.

 

1. 먼저 모든 Room 요청에 대해 (Room번호 - Room번호)로 map에 넣어놓는다
2. Room을 요청받았을 때
   1. 이미 점유된 Room인 경우 (key != value) : find() 함수를 통해 다음 Room을 재귀적으로 찾고, 해당 Room과 union한다.
   2. 점유되지 않은 Room인 경우 (key == value) : 해당 방을 바로 반환하고, 다음 Room과 union한다.
      
      • 이때 다음 Room이 map에 존재하지 않는다면 해당 Room을 map에 추가해준다.
      • 만약 map에 1번 Room은 있고 2번 Room이 없을 때, 1번 Room을 요청한 경우 다음방인 2번 Room과 union해야 하므로 생성해준 후 union한다.

 

🐢코드

import java.util.*;

class Solution {
    
    static HashMap<Long, Long> parents = new HashMap<>();
    static List<Long> answer = new ArrayList<>();
    
    public List solution(long k, long[] room_number) {
        
        for (long roomNum : room_number) 
            parents.put(roomNum, roomNum);
        
        for (long roomNum : room_number)
        {
            if (find(roomNum) == roomNum) {
                answer.add(roomNum);
                union(roomNum, find(roomNum + 1));
            } else {
                long nextRoom = find(roomNum);
                answer.add(nextRoom);
                union(roomNum, find(nextRoom + 1));
            }
        }
        return answer;
    }
    
    private static long find(long room)
    {
        if (parents.containsKey(room)) {
            if (parents.get(room) == room) return room;
            else {
                long nextRoom = parents.get(room);

                if (parents.containsKey(nextRoom)) {
                    parents.put(room, find(nextRoom));
                    return parents.get(room);
                } else
                    parents.put(room, nextRoom);
                return nextRoom;
            }
        } else {
            parents.put(room, room);
            return room;
        }
    }
    
    private static void union(long leftRoom, long rightRoom)
    {
        long left = find(leftRoom);
        long right = find(rightRoom);
        
        parents.put(left, parents.get(right));
    }
}

🐢 마무리