2019 KAKAO WINTER INTERNSHIP - 호텔 방 배정

거두절미하고 문제 갑시다 ! 다음 주 시험이니 시간이 없어요 !

 

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

코딩테스트 연습 - 호텔 방 배정

---

그 당시 이 문제 개념 없이 배열로 풀었었죠.

 

k가 10의 12승이 되니 배열의 크기 때문에 메모리가 초과하는건 당연지사.

 

그렇기 때문에 다른 방법이 필요했습니다.

 

즉, k는 그렇게 중요하지 않는 인자임을 캐치해야하며, 중요한건 손님의 원하는 방의 배열이 되겠죠. 실제로 문제를 풀 때 k를 쓰지 않았습니다.

 

배열이 아니면 어떤 자료구조를 써야할까요?

 

저는 dictionary (hash map)을 사용했습니다.

 

어떻게 했느냐?

 

예제를 통해 보시죠.

---

초기 값 full = {}라는 변수를 가집시다.

 

[1,3,4,1,3,1] 라는 예제에서 처음으로 1이 들어옵니다.

 

full에 아무도 없으니 1번 방에 손님을 채우도록 합시다. 그 다음 1번 방에 사람이 또 들어온다면 2번방으로 보내야하니 key는 1, value는 2로 full에 넣읍시다.

 

full => { 1 : 2 }

 

3, 4까지는 무난하게 흘러갑니다.

 

full => { 1: 2, 3 : 4, 4 : 5 }

 

다시 1이 나왔네요

 

저희는 이 손님을 2번 방으로 보내야합니다. 그렇다면 1번 방의 value를 참조해서 보내면 되겠군요.

 

full => { 1 : 2, 2 : 3, 3 : 4, 4 : 5 }

 

자 2번 방에 보냈는데, 부족한 걸 눈치 채셨나요? 2번 방의 목표가 1번 방의 목표가 되었다는 것을 알아야합니다. 즉, 2번 방에 사람을 넣든 1번 방에 사람을 넣든 모두 3을 바라보고 있어야한다는 소리죠. 즉 recursive하게 수정을 해줘야한다는 점입니다.

 

full => { 1 : 3, 2 : 3, 3 : 4, 4 : 5 }

 

이런 식으로요.

 

이 방법으로 문제를 통과하실 수 있습니다.

 

def solution(k, room_number):
    result = []
    h = {}
    for room in room_number:
        if h.get(room) == None:
            h[room] = room + 1
        else:
            temp = room
            while h.get(room) != None:
                room = h[room]
            h[room] = room + 1
            while temp != room:
                before = h[temp]
                h[temp] = room + 1
                temp = before
        result.append(room)
    return result

---

이상 2019 KAKAO WINTER INTERNSHIP - 호텔 방 배정였습니다. ^_^