[프로그래머스] 호텔 방 배정

※사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

프로그래머스

 

---

 

문제 설명

◇ 규칙에 따라 고객의 방을 배정하는 문제로, 규칙은 다음과 같습니다.

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

◇ 방의 개수가 10의 12승으로, 고객이 요구한 방이 비어있는지 비어있지 않는지 탐색하다간 시간 내에 문제를 풀 수 없습니다. 실제로 방이 비어있는지 여부를 하나씩 탐색한 코드는 효율성 측면을 통과하지 못합니다.

 

◇ 그럼 어떤 방식으로 접근하는게 좋을까요?

▶ 고객이 배정된 방을 딕셔너리에 저장합니다. 그 뒤 고객이 요청한 방이 딕셔너리에 있다면, 그다음 방을 찾아가고, 그다음 방도 딕셔너리에 있다면 그다음 방도 찾아가는 방식을 사용한다. 자세한 설명은 코드와 함께 덧붙이겠습니다.

 

 

 

---

문제설명 (With Python)

def solution(k, room_number):
    answer = []
    room = {}
    for c_idx in room_number:
        visited = [c_idx]
        while c_idx in room:
            c_idx = room[c_idx]
            visited.append(c_idx)
        answer.append(c_idx)
        for i in visited:
            room[i] = c_idx+1
    return answer

◇ 호텔 방(객실)에 대한 정보를 넣을 room이라는 딕셔너리를 선언합니다.

▶딕셔너리의 key 값은 고객이 배정된 방이고 value 값은 key의 다음 방 번호 입니다.

 

◇ for 문으로 고객이 요구한 방 번호가 있는 room_number를 탐색합니다. for문 안에 있는 로직을 예제로 나온 "[1,3,4,5,1,3,1]"를 사용해 자세하 설명하자면 다음과 같습니다.

1. visited라는 리스트에 확인할 방 번호 즉 방문할 방 번호를 넣습니다.

2. while문으로, c_idx(고객이 요구한 방 번호)가 room에 있는지 확인합니다.

3. 처음 고객이 요구한 방번호가 1 이므로 c_idx = 1이고, 현재 room 딕셔너리는 비어있습니다. 그러므로 첫 번째 고객은 본인이 원했던 1번 방을 배정받고, 1번 방 정보가 room에 담기게 됩니다. ( room [1] = 2(=다음에 비어있는 방))

4. 이렇게 room_number 4번까지는 배정되지 않는 방을 요구하기 때문에 3번과 같은 흐름으로 가게 되고, 그다음에 1번이 등장하면서 처음으로 중복된 방을 요청하게 됩니다. 

5. 1번 방을 요구한 고객의 요청을 보기 전에, 객실에 대한 정보를 넣은 room의 상태를 보면 다음과 같습니다.

room = {1: 2, 3: 4, 4: 5}

c_idx 가 1이고, room의 key값으로 1이 있기 때문에, while문 안으로 들어가게 됩니다. while문에서 c_idx가 room [1]의 값으로 업데이트되고, c_idx값은 2가 됩니다. 2를 visited에 넣어 추후에 방문한 방들의 다음 방 번호를 갱신할 때 사용합니다.

2는 room에 없기 때문에  while문을 빠져나오게 됩니다. 

6. 2를 answer에다 넣고, for문을 통해 visited 배열을 돕니다. 이 경우 visited배열은 [1, 2]를 가지게 되는데, 1은 기존의 c_idx의 값이고 2는 갱신된 c_idx의 값입니다.

7. for문으로 들어가 방문했던 방의 다음 방 번호를 갱신해 줍니다. room [1]의 값은 2에서 3으로 갱신 됩니다.

8. 나머지 경우도 해당 방식(이미 배정된 경우 vs 배정되지 않는 경우)을 이용해 구합니다.