Algorithm/Programmers
[Programmers] 호텔 방 배정
goakgoak
2020. 9. 2. 14:47
[2019 카카오 겨울 인턴십] 호텔 방 배정
https://programmers.co.kr/learn/courses/30/lessons/64063
Solution
- 처음에 연결리스트를 사용해서 room이 이미 선택됐을 경우 room+1 부터 순회하면서 방을 탐색하는 방식으로 구현했었는데 O(N)의 시간복잡도로는 해당 문제의 효율성 테스트를 통과할 수 없었다.
- 이후 다른 사람의 풀이에서 HashMap을 사용해 다음 방을 탐색하는 횟수를 최소로 하는 탐색 방법을 볼 수 있었다.
- map.put(선택된 방, 다음 방)으로 탐색의 시작점을 기록하는 것이다.
1. room_number 배열의 모든 원소에 대해 findEmptyRoom(int room) 함수를 호출
2. map에 room이 없는 경우는 아직 선택되지 않은 방을 뜻하기 때문에 map.put(room, room+1) 후 room을 리턴한다.
3. map에 room이 존재하는 경우 map에 미리 저장한 room의 다음 방에 대하여 빈방을 찾을 때 까지findEmptyRoom(nextRoom)를 재귀적으로 호출한다.
4. 그리고 빈 방을 찾았을 경우에 마지막으로 찾은 빈방을 처음에 호출했던 room의 다음 방으로 갱신해준다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
public class Main {
static Map<Long, Long> map = new HashMap<>();
public static long[] solution(long k, long[] room_number) {
int n = room_number.length;
long[] answer = new long[n];
for (int i = 0; i < n; i++) {
System.out.println("i = " + i);
answer[i] = findEmptyRoom(room_number[i]);
}
return answer;
}
private static long findEmptyRoom(long room) {
if (!map.containsKey(room)) { // 1. 내가 선택한 방이 map에 없음 => 선택할 수 있음
map.put(room, room + 1); // 1-1. 이미 선택된 방임을 기록하기 위해 다음 번호의 방과 함께 put
return room; // 1-2. room 그대로 return
}
long nextRoom = map.get(room); // 2. 내가 원하는 방이 map에 있음 => 다음 방 선택해야함
long emptyRoom = findEmptyRoom(nextRoom); // 2-1. 다음 방에 대해 선택 시도 => 선택 가능한 emptyRoom을 찾을 때 까지 반복됨
map.put(room, emptyRoom); // 2-2. 다음 방 갱신 작업
return emptyRoom;
}
public static void main(String[] args) throws IOException {
solution(10, new long[] {1,2,3,4,1,2});
}
static int stoi(String s) {
return Integer.valueOf(s);
}
}
|
cs |