[프로그래머스] lv4. 호텔 방 배정 (with Swift)

 오늘 lv3 경주로 건설이랑 이걸 풀었는데, 사실 나는 이것보다 lv3의 '경주로 건설'이 더 어려웠다. 이건 뭔가 컴퓨터 시스템 중에 비슷한 과정이 일어나는 부분이 있었던 것 같은데... 자세히 기억이 안난다. 컴구 아님 시프인데 기억이 안나는 거 보니 아마 컴구에서 배웠거나... 스스로 기억을 조작한 듯 하다... 아무튼 그래서 아이디어를 빨리 떠올릴 수 있었고 푸는데 거의 30분도 걸리지 않은 듯 하다....

 내가 그래프를 잘 못해서 그런것도 있지만 거의 대부분이 이게 왜 레벨4? 라고 느꼈을 만한 문제였다. 정작 푼 사람은 경주로 건설보다 호텔 방 배정이 더 적어서, 아닐 수도 있지만... 다들 너무 쉽기도 하고 어떤 알고리즘! 이렇게 분명히 쓰이는 알고리즘이 모호해서 안풀었을 수도 있을 것 같다. 중요도를 따지자면 경주로 건설(BFS 변형)이 더 중요한 문제 아닐까...

문제

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

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음([1,3,4,2,5,6])과 같이 방을 배정받게 됩니다. 전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• k는 1 이상 10^12 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.

---

결론부터 말하자면 딕셔너리를 잘 쓰면 되는 문제였다. 다음과 같이 접근했다.

[필요한 것]

1. 어떤 방이 '원하는 방보다 번호가 크면서 비어있는 방 중 가장 작은 방'인지를 계산해야 한다.

2. 빠른 속도로

3. k가 무진장 크니까 occupied/unoccupied 관리하는 변수를 방마다 할당할 수가 없다.

 

[첫 번째 아이디어]

1. 딕셔너리를 사용해서, 이미 occupy된 방의 번호를 '원호는 방보다 번호가 크면서 비어있는 방 중 가장 작은 방 번호'에 매핑한다.

2. 손님이 원하는 그 방이 비어 있는지 아닌지를 판단해야 한다. -> 딕셔너리가 nil이면 비어 있는 것으로 판단

3. 손님이 i방을 원했고 dict[i]가 nil이면, 손님에게 i방을 주고 dict[i]에 i+1을 넣는다.

4. 손님이 i방을 원했고 dict[i]가 nil이 아니면, dict[dict[i]]가 nil인지 확인한다. nil일 때까지 계속 chaining하며 따라간다. nil이 나오면 그 방을 원한 상황처럼 해결한다. (dict[chaining결과] = 결과 + 1)

 

[예시]

 

 [1, 3, 4, 1, 3, 1] 의 경우, 

1번 손님이 1번 방을 원함 -> dict[1] == nil이므로 1번방을 주고, dict[1] = 2

2번 손님이 3번 방을 원함 -> dict[3] == nil이므로 3번방을 주고, dict[3] = 4

3번 손님이 4번 방을 원함 -> dict[4] == nil이므로 4번방을 주고, dict[4] = 5

4번 손님이 1번 방을 원함 -> dict[1] == 2이고 dict[2]==nil 이므로 2번방을 주고, dict[2] = 3

5번 손님이 3번 방을 원함 -> dict[3] == 4이고 dict[4]==5이고 dict[5]==nil이므로 5번방을 주고, dict[5] = 6

6번 손님이 1번 방을 원함 -> dict[1] == 2이고 dict[2]==3이고 dict[3] == 4이고 dict[4]==5이고 dict[5]==6이고 dict[6]==nil이므로 6번방을 주고, dict[6] = 7

 

[두 번째 아이디어]

위 과정을 처음에 생각하고 구현해서 넣었는데 정확성은 빨랐지만 효율성에서 시간 초과가 났다. chaining에 한번 걸릴 때마다 걸린 chain을 압축하기로 했다.

 

 

[예시]

 [1, 3, 4, 1, 3, 1] 의 경우, 

1번 손님이 1번 방을 원함 -> dict[1] == nil이므로 1번방을 주고, dict[1] = 2

2번 손님이 3번 방을 원함 -> dict[3] == nil이므로 3번방을 주고, dict[3] = 4

3번 손님이 4번 방을 원함 -> dict[4] == nil이므로 4번방을 주고, dict[4] = 5

4번 손님이 1번 방을 원함 -> dict[1] == 2이고 dict[2]==nil 이므로 2번방을 주고, dict[2] = 3, dict[1] = 3

5번 손님이 3번 방을 원함 -> dict[3] == 4이고 dict[4]==5이고 dict[5]==nil이므로 5번방을 주고, dict[5] = 6, dict[3] = 6, dict[4] = 6

6번 손님이 1번 방을 원함 -> dict[1] == 3이고 dict[3] == 6이고 dict[6]==nil이므로 6번방을 주고, dict[6] = 7, dict[1] = 7, dict[3] = 7

* chaining 과정이 줄었다~~ miss가 많이 나는 경우에 유리하다. 효율성도 통과했다. 효율성 통과는 모든 chain을 압축하지 않아도, 일부 chain만 압축해도 나왔다. 아래에 코드

 

import Foundation

func solution(_ k:Int64, _ room_number:[Int64]) -> [Int64] {
    var dict: [Int64:Int64] = [:]
    var answer : [Int64] = []
    for i in room_number {
        var num = dict[i]
        if num == nil {
            answer.append(i)
            dict[i] = i + 1
        }
        else {
            var revise = [i, num!]
            while(dict[num!] != nil) {
                num = dict[num!]
                revise.append(num!)
            }
            for revise in revise {
                dict[revise] = num! + 1
            }
            answer.append(num!)
        }
    }
    return answer
}

 

[실제 해설]

 카카오에서 공개한 실제 해설을 보면, 좀 더 개념적인 차원에서 설명했다 뿐이지 거의 유사하게 나와 있다. 노드라는 개념을 써서 설명했는데 괜찮은 생각 방식인 것 같다. 난 딕셔너리부터 떠올렸는데 앞으로는 부모-자식 노드 구조라는 개념을 사용해서 생각해 보는 것도 좋을 듯. 가장 부모 노드를 찾아가는 과정이 내가 chaining이라고 생각한 부분이고, hashmap 등을 사용해 메모리를 절약하라는 부분도 충족! 오랜만에 마음에 드는 풀이다. 

 

더 나은 풀이가 있으면 알려주시라,,