호텔방 배정 python(카카오 2019 겨울인턴십)[프로그래머스]

문제 주소입니다.

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

프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

4. 결과

---

1. 문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 스노우타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다. 고객은 투숙하기 원하는 방 번호를 제출합니다. 고객이 원하는 방이 비어 있다면 즉시 배정합니다. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다. 예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다. 전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

k는 1 이상 1012 이하인 자연수입니다. room_number 배열의 크기는 1 이상 200,000 이하입니다. room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다. room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다. 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

예시

입출력 예

k	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

---

2. 문제풀이

효율성을 통과하지 못해서 여러가지 방식으로 시도했다. 1. 정확성만 맞추기 처음에는 간단하게 풀어보았다. 방이 사용되었는지 체크하는 리스트를 두고 방이 사용되었다면 값을 바꿔줬다. 방이 사용되었다면 다음방을 확인하고 비어있다면 그방을 answer에 추가하는 형식을 이용했다. 2. 효율성 올리기 효율성을 올리기 위해 리스트 체크용만이 아니라 특정 방을 요구했을때 이전 사람을 어디방에 배정해줬는지 확인해서 배정하는 방식으로 만들었다. 만약 2번방을 요구하는 사람이 3명이라 할때 처음사람을 2번방에 배정하고 2번째 사람을 4번방에 배정하게 되었다면 리스트에서 2번방은 5를 가르키게 된다. 효율성테스트 1,2번은 통과되었으나 나머지가 통과되지 않았다. 3. 체크하는 구조 바꾸기 room_number 가 20만인건 확인했는데 k가 10^12 인것을 나중에 확인했다. k가 극단적으로 클때 리스트를 생성하는데 시간이 걸린다 생각하여 딕셔너리를 이용했다. get 함수를 이용하여 있다면 가져오고 없다면 방을 배정해주고 다음방을 가리키도록 만들었다. 이동할때 거쳤던 방들을 리스트에 담아 보관하다가 방을 배정하게 되면 거쳤던 방들은 모두 마지막에 배정된 방 다음칸을 가리키도록 추가했다.

 

---

3. 소스코드

#Lv4 2019 겨울 인턴십
#호텔 방 배정
 
def solution(k, room_number):
    answer = []
    #체크용 딕셔너리
    room = {}
    #손님을 받으며 체크하자
    for num in room_number:
        #딕셔너리에 확인 0이라면 배정이 안됬고, 다른값이 있다면 이미 배정되었다.
        number = room.get(num, 0)
        if number :
            #임시변수에 방번호를 넣어준다,
            temp = [num]
            #반복문을 돌면서 빈방이 나올때까지 체크
            while True:
                index = number
                #이동했던 위치를 이용하여 다시 이동
                number = room.get(number, 0)
                #방이 비어있다면 방을 할당
                if not number:
                    #정답에 추가해주고
                    answer.append(index)
                    #딕셔너리에 값을 등록하고
                    room[index] = index + 1
                    #이전에 거쳤던 방들도 바꿔준다.
                    for i in temp:
                        room[i] = index + 1
                    break
                temp.append(number)
        #배정이 안되어있다면 결과추가하고 방배정 되었다고 딕셔너리에 표시
        else:
            answer.append(num)
            room[num] = num + 1
    return answer

 

 

---

4. 결과