Py) 프로그래머스 64063 호텔 방 배정

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

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

 

1. 내 접근

방번호를 인덱스로 취급해서 계산한다.

true/false로 비었는지 아닌지 여부를 판단하고,

for문 / index()를 통해 손님이 요구하는 방 번호보다 큰 번호의 방 중 최소를 찾는다.

 

2. 코드

2.1 효율성통과 못함

def solution(k, room_number):
    answer = []

    visited = [False for _ in range(k+1)]

    for room in room_number:
        if visited[room] == False:
            visited[room] = True
            answer.append(room)
        else:
            for i in range(room+1, len(visited)):
                if visited[i] == False:
                    visited[i] = True
                    answer.append(i)
                    break

    return answer

2.2 효율성 통과 못함22

def solution(k, room_number):
    answer = []
    visited = [False for _ in range(k)]

    for room in room_number:
        if visited[room-1] == False:
            visited[room-1] = True
            answer.append(room)
        else:
            idx = len(visited[:room]) + visited[room:len(visited)].index(False)
            visited[idx] = True
            answer.append(idx+1)

    return answer

* index()의 시간복잡도: O(1)

 

3. Solution

3-1. 사용 알고리즘, 자료구조: x

3-2. 사용 자료형: dictionary

3-3. 로직

1) 딕셔너리를 사용해서 배정된 방을 관리한다.

2) 처음 선택된 방(아직 배정안된)을 딕셔너리에 넣을때, value로 해당 방의 수보다 +1보다 큰 수를 넣어준다.

3) 이미 배정된 방이라면, temp 딕셔너리에 재호명된 번호를 넣어주고, 배정된 방의 그 다음 방(value +1해서 넣었으므로)이 배정되었는지 확인한다. (이런식으로 recom을 그 다음 방으로 계속 갱신)

4) 배정되었다면 temp 딕셔너리에 넣어줘서 이후 배정안된 방을 만났을 때, 배정되지 않은 위치를 각각 설정해줄 수 있게 한다.

3-4. 코드

def solution(k, room_number):
    answer = []
    room = {}

    for num in room_number:
        recom = room.get(num, 0)   # room[num]의 value (그다음 방) || 0
        if recom:      # 그 다음 방을 추천한다면?
            tmp = [num]
            while True:
                idx = recom
                recom = room.get(recom, 0)      # 갱신
                if not recom:    # 추천한 방이 비었다면
                    room[idx]= idx+1    # 으ㅏㅇ어ㅏ앙아아ㅏㅇ나아
                    answer.append(idx)
                    for i in tmp:
                        room[i] = idx + 1
                    break
                tmp.append(recom)
        else:
            room[num] = num+1
            answer.append(num)

    return answer

 

4. 피드백

room[idx] = idx+1을 room[idx]: idx+1이라고 함

....