Programmers 64063: 호텔 방배정

규칙

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

1차시도 - 가장 먼저 떠오른 풀이로는 배정된 방 리스트를 해시맵에 넣어두고 있으면 다음 번호를 리턴해주면 되지 않을까 생각했다.

아래 코드를 설명해 보자면, 이미 예약된 호텔의 경우 해시 맵에 넣고 해시맵에 있으면 다음 번호를 확인하는 식이다.

import java.util.*;
class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		HashSet<Long> reservedRoomNumber = new HashSet<Long>();
		
		for(int i=0;i<room_number.length;i++) {
			answer[i] = getRoomNumber(room_number[i], reservedRoomNumber);
		}
		
		return answer;
	}

	public long getRoomNumber(long target, HashSet<Long> reservedRoomNumber) {
		if(reservedRoomNumber.contains(target)) {
			long emptyRoom = getRoomNumber(target+1, reservedRoomNumber);
			return emptyRoom;
		}
		
		reservedRoomNumber.add(target);
		return target;
	}
}

결과는 효율성 테스트에서 전멸했다...ㅎㅎ

생각해보니 이렇게 짜면 남아있는 다음 방을 찾을 때

10번방 다음 번호로 가능한 방 번호가 100번이면 11~100번까지 순차적으로 모두 봐야하니 시간초과가 날 수밖에 없었음

=> 순차적으로 본다고 해도 다음에 같은 번호를 찾을 때에는 다시 안 보도록 어딘가 저장을 해 두자 => DP를 사용해 볼까?

 

 

2차시도 - 그렇다면 10번방 바로 다음 번호가 100번인걸 어떻게 바로 알려줄까 생각해봤다.

DP라고 하기엔 조금 애매하지만,

dp[roomNumber] = nextEmptyRoomNumber 이런식으로 저장해서 다음에는 이 배열만 access하면 되도록 만들어 봤다.

import java.util.*;
class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		long[] dp = new long[(int) (k + 1)];

		for (int i = 0; i < room_number.length; i++) {
			answer[i] = getRoomNumber(room_number[i], dp);
		}

		return answer;
	}

	public long getRoomNumber(long target, long[] dp) {
		if (dp[(int) target] == 0.0) {
			dp[(int) target] = target + 1;
			return target;
		}

		long nextRoom = dp[(int) target];
		long nextEmptyRoom = getRoomNumber(nextRoom, dp);
		dp[(int) nextRoom] = nextEmptyRoom + 1;
		return nextEmptyRoom;
	}
}

엄청 빠르다...!! 그치만 메모리 초과와 런타임 에러가 생겼다. 

왜 이런지 생각해 봤는데 일단 k는 1 이상 10^12 이하인 자연수이다. (java에서 선언할 수 있는 최대 배열 길이는 2^31 − 1이다.)

 

 

3차 시도 - Long을 key로 할 수 있는 HashMap에다가 넣자!

왜냐면 쓸데 없이 만들어진 뒤에 쓰지 않는 배열 원소가 있어서 OOME가 났기 때문이다. 풀이는 아래와 같다.

2차시도에서처럼 array를 직접 접근하지 않고 logn으로 계속 찾는 형식이기 때문에 시간은 훨씬 오래 걸리지만 통과..

hashmap 외에 treemap, linkedhashmap은 더 느리다는 것을 확인했다.

class Solution {
	public long[] solution(long k, long[] room_number) {
		long[] answer = new long[room_number.length];
		HashMap<Long, Long> roomRemainNumber = new HashMap<Long, Long>();

		for (int i = 0; i < room_number.length; i++) {
			answer[i] = getRoomNumber(room_number[i], roomRemainNumber);
		}

		return answer;
	}

	public long getRoomNumber(long target, HashMap<Long, Long> roomRemainNumber) {
		if (!roomRemainNumber.containsKey(target)) {
			roomRemainNumber.put(target, target + 1);
			return target;
		}

		long room = roomRemainNumber.get(target);
		long emptyRoom = getRoomNumber(room, roomRemainNumber);
		roomRemainNumber.put(target, emptyRoom + 1);
		return emptyRoom;
	}
}

 

배운점

2020/12/19 - [Java] - Java HashMap vs LinkedHashMap vs TreeMap

Java HashMap vs LinkedHashMap vs TreeMap