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

🔗 문제 링크

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

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

 

📝 풀이 과정

만약 방을 순차적으로 탐색한다면 시간초과가 발생하게 된다.

 

Disjoint Set과 유사한 방식으로 문제를 풀었는데, k의 범위가 $10^{12}$이기 때문에 가능한 배열의 범위를 초과해 Map을 사용해 주었다. 만약 방문하지 않은 방이라면 Map에 없기 때문에 바로 배정이 가능하고, 같은 번호가 들어온다면 다음 번호로 방을 배정해주라는 의미로 방번호 + 1을 넣어주었다. 만약 + 1한 방도 이미 Set에 들어가 있는 경우 Set에서 없을 때까지 재귀를 사용해 반환해주었다.

 

💻 코드

import java.util.*;

public class Solution {
    Map<Long, Long> map;

    public long[] solution(long k, long[] room_number) {
        map = new HashMap<>();
        long[] ans = new long[room_number.length];

        for (int i = 0; i < ans.length; i++)
            ans[i] = find(room_number[i]);

        return ans;
    }

    long find(long n) {
        long room = n;

        if (map.containsKey(room))
            room = find(map.get(room));

        map.put(n, room + 1);
        return room;
    }
}