https://school.programmers.co.kr/learn/courses/30/lessons/64063
문제
> "스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다.
> 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다.
> 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.
> 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
> 고객은 투숙하기 원하는 방 번호를 제출합니다.
> 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
> 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.
> 예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.
원하는 방 번호 배정된 방 번호
1 1
3 3
4 4
1 2
3 5
1 6
> 전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때,
> 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.접근
특정 방을 원하고자 할 때, 그 방에 이미 투숙객이 있으면 그 방보다 큰 방들 중 가장 작은 어떤 방을 가리키고 있어야 그 방을 제공해줄 수 있다.
따라서 방들은 각각 처음엔 자기 자신을 가리키고 있는다.
만약 배정이 완료되면 더 큰 방 중 가장 작은 방인 바로 다음(+1)번째 방을 가리킨다.
예를 들어 3번 방을 잡고자 했는데 이미 잡혀있다면 4번방을 가리키고 있을 것이다.
근데 4번 방도 잡혀있으면 5번방을 가리킨다.
이렇게 꼬리를 물며 가리키고 있는 방이 가리키는 방을, 즉 최종 부모를 찾아가는 방식인 것을 알 수 있다.
따라서 union-find를 활용할 수 있다.
문제해결
> 통상 쓰이는 parent 배열의 인덱스로 방의 번호가 들어가야하는데 크기가 Long이므로 불가능하다.
> 배열대신 Map을 사용하여 방번호, 가리키는 방 조합으로 저장한다.
> find 메서드 안에 union의 기능도 내포하고 있다.
> 먼저 들어온 방의 번호 f에 대해서 가리키는 방이 있는지 본다.
> 방이 없다면, 즉 아직 배정이 된 적이 없으면 해당 방이 가리키는 방을 f + 1로 주고 맵에 저장한다.
> 저장은 +1로 하여 다음을 가리키지만 배정된 방은 f이므로 이를 반환한다.
> 만약 이미 배정된 적이 있다면 조건문 밖이 실행된다.
> 먼저 부모를 찾기 위해 재귀를 통해 가리키는 방이 가리키는 최종 방을 본다.
> 맵에 들어있지 않은, 배정되지 않은 방까지 재귀가 도달하면 해당 방 번호를 return해서 p에 가져온다.
> 이때, union 기능을 해준다. 맵에 해당 방이 가리키는 방을 갱신 해준다.
> 그리고 해당 p를 반환하며 재귀를 풀어준다.
> 이는 3번 방이 4를 가리키고 , 4번 방이 5를 가리킬 때, 5번방이 새로 배정 되고 5를 반환하여
맵에 4, 5를 저장하고 5반환, 3, 5를 저장하고 5를 반환 하게 된다.
>이 find 메서드를 통해 주어진 room_number 배열을 순회하며 방을 배정한다.
> find메서드에서 반환 되는 값은 그 번째에 배정 된 방을 나타낸다.코드
import java.util.*;
class Solution {
Map<Long, Long> parent = new HashMap<>();
public long find(long f) {
if(!parent.containsKey(f)) {
parent.put(f, f + 1);
return f;
}
long p = find(parent.get(f));
parent.put(f, p);
return p;
}
public long[] solution(long k, long[] room_number) {
long[] answer = new long[room_number.length];
for(int i = 0; i < room_number.length; i++) answer[i] = find(room_number[i]);
return answer;
}
}후기
예전에 최소 신장 트리문제를 풀 때 사용했던 find-union이 생각이 났다. 연쇄적인 처리가 있어야 하고 방이 10^12므로 완전탐색이 불가능하다.
다시 구현해보니 좋았다.
