목록유파 (1)

코딩관계론

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

아이디어 도출 방법 나는 힌트를 k와 room_number의 숫자 차이로 알았다. k의 max는 10^12지만, room_number는 최대 20만이기 때문이다. 다음으로는 방의 점유 여부를 표시하기 위해서 해당 room_number을 key로 하고 value는 [점유여부, 다음 방 번호]를 가지는 dict 클래스를 생성했다. 해당하는 방 번호에 사용자가 있는지 확인하는 방법은 두 가지가 있다. 최대 O(K)만큼 돌면서 dict [room_number]을 호출하는 방식 union find 알고리즘을 사용해 O(1)에 확인하는 방법 이번 문제의 KEY는 union find short path 알고리즘을 아느냐가 제일 중요했다. Union Find short path 문제에서 초기 상태는 아래와 같이 구성된..
개발/알고리즘 2022. 12. 21. 13:54
이전 Prev 1 Next 다음