[PGR] 2019 카카오 개발자 겨울 인턴십 - 호텔 방 배정

📌 문제 링크

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

프로그래머스

 

---

문제설명

 

고객에게 호텔 방 번호를 배정할 때, 이에 최적화된 알고리즘을 통해 시간 복잡도를 개선해야 통과할 수 있는 문제였습니다. 이번 문제에서 '최대 방번호'를 찾기 위해 사용한 알고리즘은 서로소 집합, 즉 유니온 파인드 알고리즘을 사용했습니다. 소스 코드 자체는 코드량이 적어 간단한 편이나, 그 원리에 대해 설명해보도록 하겠습니다.

 

문제에서 주어지는 파라미터는 두 종류 입니다.

고객들이 희망하는 방의 번호의 최댓값을 의미하는 K,

고객들이 희망하는 방의 번호들을 담은 배열 room_number 입니다.

 

제약조건

• 한 번에 한 명씩 신청한 순서대로 방을 배정
• 고객이 원하는 방이 비었다면, 즉시 배정
• 고객이 원하는 방이 비어있지 않다면, 방보다 크면서 비어있지 않은 가장 작은 번호의 방을 배정
• k 는 1 이상 10^12 이하인 자연수
• room_number 배열의 크기는 1 이상 200,000 이하
• room_number 배열의 원소는 1 ~ k 인 자연수
• 주어진 조건을 만족할 수 없는 경우의 수는 주어지지 않음
• ex) k=5, [5,5] → 최대가 5번인데 5번을 희망하는 사람이 두 명인 경우

 

풀이설명

고객이 희망하는 방번호 배열을 순회하면서, 비어 있다면 곧바로 방을 배정해줍니다.

동시에, 배정된 방은 Map을 통해서 방의 번호 & 방번호 +1 한 값을 Key-Value 쌍으로 저장해줍니다.

이때, 배정받은 방 번호를 Key, 배정받은 방 번호에 1을 더한 값을 Value로 Map에 저장하는 이유는 추후 동일한 방을 희망하는 고객이 있을 경우, 포인터의 역할로 다음 방번호를 가리키기 위함입니다. 

 

대부분의 테스트 케이스에서 초반에는 고객이 원하는 방의 번호대로 빠르게 방을 할당 받을 수 있습니다.

그러나, 후반으로 갈수록 이미 선점한 고객과 방번호의 충돌이 일어나게 되고, 이때 Map으로 저장해 둔 Key-Value 쌍을 통해서 빠르게 값을 찾게 됩니다. 이때 빈 방 번호를 찾는 알고리즘이 바로 Union-Find  이고,  시간 복잡도는 평균 O(a(N)) 으로 상수 시간 복잡도에 가깝습니다.

 

https://8iggy.tistory.com/157

서로소 집합(Disjoint Set), 유니온 파인드(Union-Find)

 

따라서, 효율성 테스트 케이스가 있는 이번 문제에서 시간 복잡도를 줄이는 데 알맞은 알고리즘이라고 볼 수 있겠습니다.

 

아래의 그림을 보면 주어진 테스트 케이스에서 초반에는 원하는 대로 방을 배정받는 것을 확인할 수 있습니다.

 

---

그러나, 후반으로 갈수록 고객이 원하는 방을 배정받을 확률은 줄어들게 되고,

다음의 그림처럼 중반부 이후부터는 거의 100% 원하는 방을 배정 받지 못하며, Union-Find 알고리즘을 통해 빈 방을 찾는 작업이 필요할 확률이 증가하는 것을 확인할 수 있습니다.

 

---

다음으로 위에서 설명한 알고리즘을 구현한 소스코드는 아래와 같습니다.

 

소스코드

import java.util.*;

class Solution {
   
   // 비어있는 방을 찾기 위한 Union-Find 메서드, Map을 사용해서 탐색!
   private static long findParent(HashMap<Long, Long> table, long x){
        if(table.getOrDefault(x, -1L) < 0L ) {
            table.put(x, x+1);
            return x;
        }else {
            table.put(x, findParent(table, table.get(x)));
            return table.get(x);
        }
    }


    public long[] solution(long k, long[] room_number) {        
        long[] answer = new long[room_number.length]; // 정답 배열을 선언하고
        HashMap<Long, Long> hmap = new HashMap<>(); // 빈 해쉬맵으로 출발

		// 고객의 수만큼 순회하면서
        for(int i = 0, size = room_number.length ; i <  size ; i++){
            long res = findParent(hmap, room_number[i]); // 메서드를 통해 배정 번호를 받고
            // 내부적으로 배정받은 번호 + 1 을 hmap에 저장하는 로직이 포함되어 있음!
            answer[i] = res; // 배정받은 번호를 배열에 기록한다.
        }

        return answer; // 정답 배열을 리턴
    }   
}