프로그래머스_호텔 방 배정 <Java>

문제 설명

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

원하는 방 번호 배정된 방 번호

1	1
3	3
4	4
1	2
3	5
1	6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• k는 1 이상 10^12 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

 

문제 풀이

문제는 직관적으로 이해가 쉽다. 하지만 k의 최대값이 1조인 점을 어떻게 고려하여 적용할 지가 가장 큰 과제였다.

초기엔 제시된 배열의 순서대로 방문한 적이 있냐 없냐, visited의 형태를 고려하였지만, 메모리 공간 초과라는 결과에 잘못된 것임을 깨닫게 되었다.

 

숫자의 범위가 1조까지라는 점, 배열의 크기는 20만개였기 때문에 1조라는 숫자까지 모든 배열을 만들 필요가 없었다. 따라서 각 숫자마다 다음 방을 지칭하는 LinkedList나 HashMap을 활용하는 게 적절한 방법이라 생각했다. 하지만 LinkedList의 경우 다음 방의 값이 삭제되고 추가되는 경우가 빈번할 것이라 판단하여 HashMap을 사용하기로 결정하였다.

 

또한 방 번호가 서로 연결된 집합 형태로 관리하기 위한 자료구조인 Union-Find를 활용하여 시간 효율성을 최대화했다.

 

 

코드 구현

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

class Solution {
    
    static long[] answer;
        
    public long[] solution(long k, long[] room_number) { //전체 방 k개, 원하는 room_number 순으로
        
        int roomSize = room_number.length; // 배열의 크기는 20만 이하
        answer = new long [roomSize];
        
        HashMap<Long, Long> parent = new HashMap<>();
        
        for(int i = 0 ; i < roomSize; i++){
            long room = room_number[i];
            answer[i] = findParent(parent,room);
        }
            
        return answer;
    }
    
    private long findParent(HashMap<Long, Long> parent, long room){
        if(!parent.containsKey(room)) {
            parent.put(room,room +1);
            return room;
        }
        
       long nextRoom = findParent(parent, parent.get(room));
        parent.put(room, nextRoom); // 경로 압축
        return nextRoom;
    }
    
}