🌿 나의 풀이
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
반응형
'coding test' 카테고리의 다른 글
[파이썬, Java] 쿠키 구입 (0) | 2023.04.12 |
---|---|
[파이썬, Java] 인사고과 (0) | 2023.04.12 |
[파이썬] 부대복귀 (0) | 2023.04.11 |
[파이썬] 호텔 대실 (0) | 2023.04.10 |
[파이썬] 과제 진행하기 (0) | 2023.04.05 |