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

문제

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

코딩테스트 연습 - 호텔 방 배정

 

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 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] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

풀이

전체 방의 개수가 10^12 이므로, 해당 문제는 완전탐색이 불가능한 문제이다.

Union-Find 기법 힌트를 보고 풀 수 있었다. 

 

Union-find 사용 문제

2021.10.23 - [Problem Solving/BOJ] - [BOJ 20040] 사이클 게임 (Java)

[BOJ 20040] 사이클 게임 (Java)

Union-find 구현

• MakeSet(): parent, rank 초기값 설정
  • parent는 자기 자신, rank는 0으로 초기화
• Find(a): 원소 a의 parent node (root node)를 리턴
  • path-compression 기법으로 중간 가지를 없애고 parent로 root node를 저장하고 리턴하도록 구현
• Union(a, b): 원소 a와 b를 동일한 집합으로 묶는다.
  • rank가 큰 node가 작은 node의 parent가 되도록 설정
  • 만약 rank가 같다면 한쪽의 rank를 증가시켜 parent가 되도록 설정
  • 매개 변수 a와 b의 parent node로 관계 설정

 

해당 문제에서 Union은 아래 내용을 반영하여 구현하였다. 

• 무조건 a보다 b에 더 큰 값을 넣을 거라, a의 parent가 b가 되도록 하였다.
• 새롭게 추가되는 방은 Union 시 parent 값을 초기화 해주었다. 
• (k가 10^12이므로 미리 모든 방의 parent를 초기화하면 시간 초과)
• union 시 무조건 번호가 큰 방이 parent가 되는 것을 알고 있으므로 rank 자료 구조는 만들지 않았다.

 

소스코드

import java.util.*;
class Solution {
    public HashMap<Long, Long> parent;
    public long[] solution(long k, long[] room_number) {
        ArrayList<Long> answer = new ArrayList<Long>();
        
        parent = new HashMap<Long, Long>();
        for(long room : room_number){
            parent.put(room, room);
        }
        
        for(long room: room_number){
            if(parent.get(room) == room){
                // 비어 있는 방이라면?   
                answer.add(room);
                union(room, room+1);
            } else {
                // 비어 있지 않은 방이라면 ? 
                // root를 찾아서...
                long root = find(room);
                union(root, root+1);
                answer.add(root);
            }
        }
        
        
        return answer.stream().mapToLong(x->x).toArray();
    }
    
    public Long find(Long a){
        if(parent.get(a) == a) return a;
        parent.put(a, find(parent.get(a)));
        return parent.get(a);
    }
    
    public void union(Long a, Long b){
        if(!parent.containsKey(b)){
            parent.put(b, b);
        }
        a = find(a);
        b = find(b);
        parent.put(a, b);
             
    }
}