호텔 방 배정 (64063번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 호텔 방 배정 (64063번)

자료구조&알고리즘 : 유니온 파인드 (Union Find)

난이도 : Lv 4

 

---

 

2019 카카오 개발자 겨울 인턴십 기출문제이다.

오랜만에 유니온 파인드를 활용해서 풀 수 있는 문제였다.

(유니온 없이 파인드만 적용했다.)

 

import sys
sys.setrecursionlimit(pow(10, 9))


class Hotel():
    def __init__(self, query):
        self.memo = {}
        for i in range(len(query)):
            self.memo[query[i]] = self._find(query[i])
            query[i] = self.memo[query[i]] - 1
        self.query = query
    
    
    def _find(self, q):
        p = self.memo.get(q, -1)
        if p == -1:
            return q+1
        self.memo[p] = self._find(p)
        return self.memo[p]


def solution(k, room_number):
    hotel = Hotel(room_number)
    return hotel.query

 

 

★ 문제 입출력 예 : [1,3,4,1,3,1]

 

 

① [1,3,4,1,3,1]

정답 : [1]

memo : {} → {1: 2}

→ 현재 사람을 비어있는 1번 방에 배정하고

memo[1]에, 1 다음 방인 2를 저장한다. ○

 

 

② [1,3,4,1,3,1]

정답 : [1, 3]

memo : {1: 2} → {1: 2, 3: 4}

→ 현재 사람을 비어있는 3번 방에 배정하고

memo[3]에, 3 다음 방인 4를 저장한다. ○

 

 

③ [1,3,4,1,3,1]

정답 : [1, 3, 4]

memo : {1: 2, 3: 4} → {1: 2, 3: 4, 4: 5}

→ 현재 손님을 비어있는 4번 방에 배정하고

memo[4]에, 4 다음 방인 5를 저장한다. ○

 

 

④ [1,3,4,1,3,1]

정답 : [1, 3, 4, 2]

memo : {1: 2, 3: 4, 4: 5} → {1: 3, 2: 3, 3: 4, 4: 5}

→ 현재 1번 방은 비어있지 않으므로, memo[1]을 확인한다.

memo[1] = 2 번 방은 비어있으므로 현재 손님에게 2번 방을 배정하고, memo[2]에 2 다음 방인 3을 저장한다. ○

여기서, Find를 통해 memo[1]에도 3을 저장한다. ○

 

 

⑤ [1,3,4,1,3,1]

정답 : [1, 3, 4, 2, 5]

memo : {1: 2, 3: 4, 4: 5} → {1: 3, 2: 3, 3: 6, 4: 6, 5: 6}

→ 현재 3번 방은 비어있지 않으므로, memo[3]을 확인한다.

memo[3] = 4 번 방도 비어있지 않으므로, memo[4] = 5번 방을 확인한다.

5번 방은 비어있으므로 현재 손님에게 5번 방을 배정하고, memo[5]에 5 다음 방인 6을 저장한다. ○

여기서, Find를 통해 memo[3] 과 memo[4] 에도 6을 저장한다. ○

(현재 손님에게 배정할 빈 방인 5번 방을 찾기 위해 거쳐온 방이 3, 4번 방이기 때문이다.)

 

 

⑥ [1,3,4,1,3,1]

정답 : [1, 3, 4, 2, 5, 6]

memo : {1: 3, 2: 3, 3: 6, 4: 6, 5: 6}  → {1: 7, 2: 3, 3: 7, 4: 6, 5: 6, 6: 7}

→ 현재 1번 방은 비어있지 않으므로, 빈 방을 찾을 때까지 memo를 타고 거슬러 올라간다.

1번과 3번 방을 거쳐서, 6번 방이 비어있음을 확인하고, 현재 손님에게 6번 방을 배정한다.

memo[6]에 6 다음 방인 7을 저장한다. ○

여기서, Find를 통해 memo[1] 과 memo[3] 에도 7을 저장한다. ○

(현재 손님에게 배정할 빈 방인 6번 방을 찾기 위해 거쳐온 방이 1, 3번 방이기 때문이다.)