문제 링크

🤔 풀이 방법

풀이 방법: TreeSet + LinkedHashSet

TreeSet을 사용하는 이유

TreeSet을 쓰는 이유는 아래 표의 ceiling이 핵심이다.
출처: 자바 트리셋(TreeSet) 완벽한 사용법 정리1

왜 ceiling이 핵심이냐 하면 문제의 조건 중,4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다. 때문이다.

LinkedHashSet을 사용하는 이유

• 입력된 값의 순서를 유지시키기 위해
• array보다 set이 contains의 성능이 빠르다고 한다.
  출처: Performance of contains() in a HashSet vs ArrayList

👉 소스 코드

import java.util.*
class Solution {
        val nextRoom = TreeSet<Long>()

    fun solution(k: Long, room_number: LongArray): LongArray {
        val ret = LinkedHashSet<Long>()

        for (i in room_number.indices) {
            val current = room_number[i]

            //현재 방이 찼는 지 확인
            if (ret.contains(current)) {
                //현재 방이 찬 경우
                val nRoom = nextRoom.ceiling(current) ?: current + 1

                //다음 방을 배정
                ret.add(nRoom)
                nextRoom.remove(nRoom)

                if (!ret.contains(nRoom + 1))
                    nextRoom.add(nRoom + 1)

            } else {
                //현재 방이 안 찬 경우
                ret.add(current)

                nextRoom.remove(current)

                //다음 빈 방을 넣는다.
                if (!ret.contains(current + 1))
                    nextRoom.add(current + 1)
            }
        }

        return ret.toTypedArray().toLongArray()
    }
}