[Programmers] 2019 카카오 인턴십 4번 - 호텔 방 배정

[문제 설명]

고객들이 배정 요청한 방 번호가 배열로 주어진다.

원하는 방이 비어있다면 즉시 배정한다.

비어 있지 않다면, 요청 번호보다 큰 비어 있는 방 중 가장 번호가 작은 방을 배정한다.

 

[조건]

1 <= 방 번호 <= 1,000,000,000,000

1 <= 고객의 수 <= 200,000

배정이 가능한 경우만 주어진다.

 

[풀이]

문제의 내용은 간단하다.

다만 방 번호의 범위가 아주 크다.

또한 고객의 수가 20만이라, 제곱의 시간복잡도로는 해결할 수 없다.

 

HashMap을 사용하여 풀이하였다. (하단 코드의 table 변수)

그리고, 하단과 같은 의미를 갖는다.

table<key, value> : 방 번호 key의 요청이 오면,  value로 안내

만약 처음 입력된 방 번호 (a) 의 요청이 없었을 경우에는 table에 (a, a + 1)로 저장된다.

만약 이전에 입력된 방 번호 (b)의 요청이 있었을 경우에는 table에 b의 value 값으로 이동하고, 그 value가 key가 되어서, 해당 key로 저장된 데이터가 없을 때까지 탐색한다. (하단 코드의 search 변수)

 

disjoint set과 유사한 개념인데, 방 번호가 long 의 범위라, 배열로 해결할 수는 없었다.

 

import java.util.Arrays;
import java.util.HashMap;

public class Programmers_kakao2019_intern_4 {
	static HashMap<Long, Long> table;
	
	static long search(long cur) {
        // 다음에 cur 번호로 요청이 올 경우, cur + 1로 안내
		if (!table.containsKey(cur)) {
			table.put(cur, cur + 1);
			return cur + 1;
		}
		else {
			table.put(cur, search(table.get(cur)));
			return table.get(cur);
		}
	}
	
	public static long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		table = new HashMap<Long, Long>();
		
		for (int r = 0; r < room_number.length; ++r) {
			// 해당 번호에 처음 입력하는 경우
			if (!table.containsKey(room_number[r])) {
				answer[r] = room_number[r];
				table.put(room_number[r], room_number[r] + 1);
			}
			// 이전에 들어온 경험이 있는 경우
			else {
				table.put(room_number[r], search(table.get(room_number[r])));
				answer[r] = table.get(room_number[r]) - 1;
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		System.out.println(Arrays.toString(solution(10, new long [] {1, 3, 4, 1, 3, 1})));
	}
}

 

 

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

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