[파이썬, Java] 호텔 방 배정

🌿 나의 풀이

import java.util.*;

class Solution {
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        Map<Long, Long> map = new HashMap<>();
        
        for(int i = 0; i < room_number.length; i++){
            answer[i] = dfs(room_number[i], map);
        }
    
        return answer;
    }
    
    public long dfs(long number, Map<Long, Long> map) {
        if(!map.containsKey(number)){       // 빈 방이 있으면
            map.put(number, number + 1);
            return number;
        }
        long result = dfs(map.get(number), map);
        map.put(number, result);
        return result;
    }
}

재귀

HashMap은 순서가 보장되지 않는다. ➡️ 그래서 long 배열에 담았다.

LinkedHashMap을 사용하면 넣은 순서대로 보장할 수 있다!

빈방이 있으면 빈방 : 그 다음 빈방을 넣는다.

재귀가 끝나고 돌아갈 때 해시의 값을 갱신

 

 

# 효율성 실패
def solution(k, room_number):
    answer = []
    rooms = [0] * (k + 1)
    
    for number in room_number :
        if rooms[number] == 0 :
            rooms[number] = 1
            answer.append(number)
        else :
            for j in range(number + 1, k+1) :
                if rooms[j] : continue
                rooms[j] = 1
                answer.append(j)
                break
    return answer

else문 안의 for문까지 실행되면 시간 복잡도가 상당히 커진다.

비어있지 않은 방들도 순차적으로 탐색하는 게 문제다.

 

 

🐎 다른 사람 풀이

# https://m.blog.naver.com/js568/221957852279
import sys
sys.setrecursionlimit(10000)    # 재귀 허용깊이 임의로 지정

def solution(k, room_number):
    rooms = dict()  # {방번호 : 바로 다음 빈방 번호}
    for num in room_number :
        chk_in = find_emptyroom(num, rooms)
    return list(rooms.keys())

def find_emptyroom(chk, rooms) :    # 재귀함수
    if chk not in rooms.keys() :        # 빈 방이면
        rooms[chk] = chk + 1        # rooms에 새 노드 추가
        return chk      # 요청한 방
    empty = find_emptyroom(rooms[chk], rooms)   # 재귀함수 호출
    rooms[chk] = empty + 1      # (배정된 방 + 1)을 부모 노드로 변경
    return empty        # 새로 찾은 빈 방

재귀 사용

딕셔너리에 방 번호 : 그 다음 빈방 번호를 넣는다. ➡️ 바로 다음 빈방을 찾을 수 있다.

 

 

문제 출처 👇

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

프로그래머스