호텔 방 배정

호텔 방 배정
2019 카카오 개발자 겨울 인턴십
1061명 완료

힌트를 하나 드리자면 

그래프 문제입니다. 

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

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

개념 정리만 해봅니다.

def solution(k, room_number):
    room = list(0 for _ in range(k + 1))
    for i in range(len(room_number)):
        for j in range(room_number[i], k):
            if room[j] == 0:
                room[j] = 1
                room_number[i] = j
                break
    return room_number

정확성 점수라도 확보해보자는 거죠.

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.8MB)
테스트 3 〉	통과 (0.04ms, 10.6MB)
테스트 4 〉	통과 (0.16ms, 10.7MB)
테스트 5 〉	통과 (0.05ms, 10.7MB)
테스트 6 〉	통과 (0.06ms, 10.8MB)
테스트 7 〉	통과 (0.08ms, 10.8MB)
테스트 8 〉	통과 (0.05ms, 10.7MB)
테스트 9 〉	통과 (0.05ms, 10.8MB)
테스트 10 〉	통과 (0.04ms, 10.7MB)
테스트 11 〉	통과 (0.04ms, 10.8MB)
테스트 12 〉	통과 (0.08ms, 10.6MB)
테스트 13 〉	통과 (0.05ms, 10.6MB)
테스트 14 〉	통과 (0.05ms, 10.7MB)
테스트 15 〉	통과 (0.08ms, 10.7MB)
테스트 16 〉	통과 (0.10ms, 10.7MB)
테스트 17 〉	통과 (0.11ms, 10.7MB)
테스트 18 〉	통과 (0.23ms, 10.8MB)
테스트 19 〉	통과 (0.35ms, 10.8MB)
테스트 20 〉	통과 (0.43ms, 10.9MB)
테스트 21 〉	통과 (1.01ms, 10.9MB)
테스트 22 〉	통과 (0.96ms, 10.9MB)
테스트 23 〉	통과 (1.17ms, 10.9MB)
테스트 24 〉	통과 (0.92ms, 11MB)
테스트 25 〉	통과 (0.06ms, 10.6MB)
테스트 26 〉	통과 (0.11ms, 10.7MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
채점 결과
정확성: 78.8
효율성: 0.0
합계: 78.8 / 100.0

이제 맘을 비우고 카카오 해설을 볼까요?

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

그래프 문제였군요... 
그래프는 보통 딕셔너리나 딕셔너리 + 셋을 이용하죠. 

https://comdoc.tistory.com/entry/22-%EA%B7%B8%EB%9E%98%ED%94%84

이 문제의 해설을 보니 딕셔너리로 가능하겠군요..
후닥닥 작성해 봅니다.

def solution(k, room_number):
    room = {}
    for i, num in enumerate(room_number):
        if num not in room:
            # room_number[i] = num
            # print(f"{i} 번 맴버에게 {num} 방 배정")
            room[num] = num + 1
            # print(f"{num}방의 노드에 {num + 1} 설정")
        else:
            while num in room:
                # print(f"{num} is in room")
                num = room[num]
            room[room_number[i]] = num
            # print(f"{room_number[i]}방의 노드에 {num} 설정")
            room_number[i] = num
            # print(f"{i}번 맴버에게 {num}방 배정")
            room[num] = num + 1
            # print(f"{num}방의 노드에 {num + 1} 설정")
            # print(room)
    return room_number

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.9MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.09ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.05ms, 10.7MB)
테스트 7 〉	통과 (0.07ms, 10.6MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.06ms, 10.7MB)
테스트 10 〉	통과 (0.04ms, 10.8MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
테스트 12 〉	통과 (0.05ms, 10.7MB)
테스트 13 〉	통과 (0.05ms, 10.7MB)
테스트 14 〉	통과 (0.04ms, 10.7MB)
테스트 15 〉	통과 (0.06ms, 10.7MB)
테스트 16 〉	통과 (0.07ms, 10.7MB)
테스트 17 〉	통과 (0.08ms, 10.7MB)
테스트 18 〉	통과 (0.12ms, 10.9MB)
테스트 19 〉	통과 (0.22ms, 10.8MB)
테스트 20 〉	통과 (0.27ms, 10.8MB)
테스트 21 〉	통과 (0.49ms, 11MB)
테스트 22 〉	통과 (0.52ms, 11MB)
테스트 23 〉	통과 (0.42ms, 11MB)
테스트 24 〉	통과 (0.59ms, 11.1MB)
테스트 25 〉	통과 (0.05ms, 10.7MB)
테스트 26 〉	통과 (0.07ms, 10.6MB)
효율성  테스트
테스트 1 〉	통과 (796.04ms, 310MB)
테스트 2 〉	통과 (1031.12ms, 310MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	통과 (2486.65ms, 313MB)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	통과 (1484.75ms, 313MB)
채점 결과
정확성: 78.8
효율성: 12.1
합계: 90.9 / 100.0

시간을 더 줄여야 하네요..
작성하면서도 찝찝한 부분이 한 군데 있었는데요... 
while 문에서 구멍이 좀 있었죠?
리스트를 이용 꼼꼼하게 막았습니다.
코드도 한번 더 정리..
성공~!

def solution(k, room_number):
    room = {}
    for i, num in enumerate(room_number):
        if num in room:
            path = []
            while num in room:
                path.append(num)
                num = room[num]
            for each in path:
                room[each] = num
            room_number[i] = num
        room[num] = num + 1
    return room_number

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.8MB)
테스트 3 〉	통과 (0.04ms, 10.7MB)
테스트 4 〉	통과 (0.09ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.8MB)
테스트 6 〉	통과 (0.05ms, 10.7MB)
테스트 7 〉	통과 (0.05ms, 10.7MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.04ms, 10.7MB)
테스트 10 〉	통과 (0.04ms, 10.7MB)
테스트 11 〉	통과 (0.04ms, 10.7MB)
테스트 12 〉	통과 (0.05ms, 10.8MB)
테스트 13 〉	통과 (0.04ms, 10.7MB)
테스트 14 〉	통과 (0.04ms, 10.6MB)
테스트 15 〉	통과 (0.07ms, 10.8MB)
테스트 16 〉	통과 (0.09ms, 10.7MB)
테스트 17 〉	통과 (0.09ms, 10.7MB)
테스트 18 〉	통과 (0.17ms, 10.8MB)
테스트 19 〉	통과 (0.29ms, 10.9MB)
테스트 20 〉	통과 (0.33ms, 10.9MB)
테스트 21 〉	통과 (0.61ms, 10.8MB)
테스트 22 〉	통과 (0.69ms, 11MB)
테스트 23 〉	통과 (0.49ms, 11.1MB)
테스트 24 〉	통과 (0.76ms, 11MB)
테스트 25 〉	통과 (0.05ms, 10.7MB)
테스트 26 〉	통과 (0.07ms, 10.7MB)
효율성  테스트
테스트 1 〉	통과 (356.20ms, 310MB)
테스트 2 〉	통과 (387.43ms, 310MB)
테스트 3 〉	통과 (333.77ms, 310MB)
테스트 4 〉	통과 (286.74ms, 310MB)
테스트 5 〉	통과 (126.98ms, 313MB)
테스트 6 〉	통과 (351.40ms, 312MB)
테스트 7 〉	통과 (386.64ms, 313MB)

속도도 잘 나오고 좋네요.
몇 줄 더 줄일 수도 있지만.
속도가 잘 나오지 않아서 패스.

주석을 포함한 코드입니다. 

def solution(k, room_number):
    room = {}
    for i, num in enumerate(room_number):
        if num in room:
            path = []
            while num in room:
                print(f"{num} is in room -> {room[num]}")
                path.append(num)
                num = room[num]
            for each in path:
                room[each] = num
            print(f"{path}번 방의 노드에 {num} 설정")
            room_number[i] = num
        print(f"{i}번 맴버에게 {num}방 배정")
        room[num] = num + 1
        print(f"{num}방의 노드에 {num + 1} 설정")
        print(room)
    return room_number