[Swift] 2019 KAKAO WINTER INTERNSHIP 호텔 방 배정

Problem

 

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

---

Solution

 

1. 연속된 방들의 시작과 길이를 저장해 놓을 클래스를 만든다.

 

이 문제의 핵심은 투숙을 원하는 방이 중복되었을 때 해당 방보다 크면서 가장 작은 방을 찾는 것이기 때문에 

 

연속된 방의 길이와 시작된 방의 위치를 더해주면 쉽게 찾을 수 있습니다.

 

예를 들면 10개의 방 중 2,3,4,5 가 이미 차있다면 시작된 방의 위치는 2이고 연속된 방의 길이는 4입니다.

 

고로 2,3,4,5 중에 중복된 방이 있다면 2(시작된 방의 위치) + 4(연속된 방의 길이) = 6이므로 6번 방에 넣으면 됩니다.

 

class Room {
    var root:Int64,length:Int64
    init(root:Int64,length:Int64) {
        self.root = root
        self.length = length
    }
}

 

2. 방이 비어있고 왼쪽 방이 비어있지 않은 경우를 업데이트 한다.

 

투숙될 방이 비어있고, 왼쪽 방이 비어있지 않다면 투숙될 방과 왼쪽 방을 연겴시켜 주어야 합니다.

 

즉, 현재 투숙될 방의 시작 번호를 왼쪽 방의 시작 번호로 바꾸고 연속된 방의 길이를 왼쪽 방의 길이에 +1(현재 방)으로 업데이트 해줍니다.

 

func updateLeftSide(_ n:Int64) {
    dic[n-1]!.length += 1
    dic[n] = dic[n-1]!
}

 

3. 방이 비어있고 오른쪽 방이 비어있지 않은 경우를 업데이트 한다.

 

투숙될 방이 비어있고, 오른쪽 방이 비어있지 않다면 투숙될 방을 시작으로 하고 오른쪽 방과 연결시켜 주어야 합니다.

 

그리고 방의 길이를 + 1(현재 방)으로 업데이트 해줍니다.

 

func updateRightSide(_ n:Int64) {
    dic[n+1]!.length += 1
    dic[n+1]!.root = n
    dic[n] = dic[n+1]!
}

 

4. 방이 비어있고 오른쪽과 왼쪽이 모두 비어있지 않은 경우를 업데이트 한다.

 

투숙될 방이 비어있고 왼쪽 방과 오른쪽 방이 비어있지 않다면 현재 방과 오른쪽 방의 시작을 왼쪽 방의 시작 번호 바꾸고,

 

왼쪽방의 길이와 오른쪽 방의 길이 + 1(현재방)으로 업데이트 해줘야 합니다.

 

func updateBothSide(_ n:Int64) {
    let newLength = dic[n-1]!.length + dic[n+1]!.length + 1
    dic[n-1]!.length = newLength
    dic[n+1]! = dic[n-1]!
    dic[n] = dic[n-1]
}

 

5. 방이 비어있지 않은 경우를 업데이트 한다.

 

방이 비어있지 않은 경우는 1번에서 정한 규칙대로 방의 위치를 정합니다.

 

하지만 새롭게 정해진 방의 위치 또한 2,3,4번으로 양 쪽의 방이 비어있는지 확인해준 뒤 업데이트 해줍니다.

 

func updateOverlap(_ n:Int64) {
    let newNumber = dic[n]!.root + dic[n]!.length
    check(newNumber)
}

 

* check

func check(_ n:Int64) {
    if dic[n] == nil {
        if dic[n-1] != nil && dic[n+1] != nil{
        updateBothSide(n)
        }else if dic[n-1] != nil {
         updateLeftSide(n)
        }else if dic[n+1] != nil {
         updateRightSide(n)
        }else {
            dic[n] = Room(root: n, length: 1)
        }
        result.append(n)
    }else {
        updateOverlap(n)
    }
}

---

Source Code