[프로그래머스] 호텔 방 배정 / 2019 카카오 개발자 겨울 인턴십 - JAVA

🖇️ 문제 링크

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

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다. 고객은 투숙하기 원하는 방 번호를 제출합니다.

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

 

---

📝 문제 분석

처음에는 Set에 배정이 된 방 번호를 넣어두고, 원하는 방이 Set에 없을 때까지 + 1하는 방식으로 했었는데 효율성에서 시간초과가 났다.

 

시간을 줄이기 위해서, Map<key, value> 형태로 key번 방 배정을 요청했을 때 마지막에 실제로 배정된 방 번호 + 1을 저장해놓고 매번 + 1을 하지않고 바로 배정받을 수 있는 방을 찾는 형태로 구현하였다.

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    Map<Long, Long> map = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] ans = new long[room_number.length];
        int idx = 0;
        for(long n : room_number) 
           	ans[idx++] = solve(n); 
        
        return ans;
    }
    
    public long solve(long n) {
       	long tmp = n; 
        
        if(map.containsKey(tmp))
            tmp = solve(map.get(tmp));
        
        map.put(n, tmp + 1);
        return tmp;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0