[Programmers] 호텔 방 배정

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/64063

프로그래머스

Union Find를 이용하여 풀어야 하는 문제였습니다.

k의 범위가 큰 것을 보고 이분탐색으로 접근했다가 도저히 모르겠어서 ChanBLOG님 글을 참고하여 풀 수 있었던 문제였습니다.

https://chanhuiseok.github.io/posts/prog-1/

[2019 카카오 겨울인턴십] 호텔 방 배정

 

알고리즘은 아래와 같습니다.

1. 고객이 원하는 방을 key, 배정할 수 있는 방을 value로 저장하는 unordered_map을 선언합니다.

1.1 전역 변수로 선언하여 key 값이 없을 경우 value를 0으로 반환하도록 하여 쉽게 해당 방을 배정할 수 있는지 여부를 판단할 수 있도록 합니다.

2. 고객이 원하는 방이 비어있을 경우 고객에게 해당 방을 배정해주고 unordered_map에 해당 방의 value를 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방으로 저장해줍니다.

2.1 이를 위해서 Union Find가 필요한데 findRoom 메서드를 통해 find 연산을 진행할 때마다 재귀적으로 그 이전의 노드들의 부모 노드를 모두 맨 위 루트 노드로 연결시켜주는 경로 압축을 진행합니다.

3. room_number 벡터 내 모든 방에 대해 2번을 진행해주고 answer를 반환해줍니다.

 

글로 된 설명만으로는 부족할 수 있다싶어 주어진 테스트 케이스에 대해 간단하게 그림으로 그려봤습니다.

 

 

 

 

 

 

 

 

비고

해당 문제를 map으로 이용해서 풀 경우 시간 초과가 발생합니다.

이와 관련해서는 아래 게시글을 참고해주세요.

https://jaimemin.tistory.com/2168

[C++ STL] map vs unordered_map

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~