[프로그래머스] 호텔 방 배정 (LV.4/JAVA)

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

프로그래머스

 

[문제 해석]

 

호텔에는 방이 총 k개, 1번부터 k번까지. 처음에는 모든 방이 비어있으며 아래 기준에 따라 배정.

 

한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
고객은 투숙하기 원하는 방 번호를 제출합니다.
고객이 원하는 방이 비어 있다면 즉시 배정합니다.
고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

 

 

[제한사항]
k는 1 이상 10의 12승 이하인 자연수입니다.
room_number 배열의 크기는 1 이상 200,000 이하입니다.
room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

 

 

[문제풀이]

처음에 보고 레벨4치고는 쉽다고 생각했는데. 정답률도 높네요.

특이한 건 k의 제한 범위? 10의 12승...?

그리고 효율성이 같이 있는 문제라 시간 초과를 신경써야겠네요.

 

import java.util.*;

class Solution {
    Map<Long,Long> rooms = new HashMap<Long,Long>(); //룸넘버, 다음룸넘버
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        
        for (int i=0; i<room_number.length; i++) {
            answer[i] = checkRoom(room_number[i]);
        }
        
        return answer;
    }
    
    private long checkRoom (long num) {
        long empty = 0;
        
        if (!rooms.containsKey(num)) {
            empty = num;
            rooms.put(num, num+1);
        } else {
            empty = checkRoom(rooms.get(num));
        }
        
        return empty;
    }
}

 

 

 

하지만 틀렸죠?

 

 

정확히는 효율성 검사가 실패했습니다.

모든 테스트 케이스가 실패하는 걸 보고 코드를 다시 보니...

 

이상하다는 생각은 있었지만 바로 k가 문제입니다.

현재 코드는 배정되었는지 아닌지만 체크하다보니

다음 방까지 무한하게 재귀함수를 돌려야 하며, 이게 시간 초과의 원인입니다.

 

배정 받고 싶은 방 번호가 1번인데

이미 500000000까지 전부 배정이 되었다면

500000001을 찾기 위해 재귀함수를 500000000번을 실행해야 합니다.

 

그렇다면 어디까지 배정 되어있는지 새로 업데이트 해줄 필요가 있습니다.

 

 

import java.util.*;

class Solution {
    Map<Long,Long> rooms = new HashMap<Long,Long>(); //룸넘버, 다음룸넘버
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];
        
        for (int i=0; i<room_number.length; i++) {
            answer[i] = checkRoom(room_number[i]);
        }
        
        return answer;
    }
    
    private long checkRoom (long num) {
        long empty = 0;
        
        if (!rooms.containsKey(num)) {
            empty = num;
            rooms.put(num, num+1);
        } else {
            empty = checkRoom(rooms.get(num));
            rooms.put(num, empty+1); //다음에 동일한 방 번호가 들어오면 배정될 위치
        }
        
        return empty;
    }
}

 

 

한 줄을 추가해주면 무사히 효율성까지 통과할 수 있습니다.