문제 요약
고객의 대실 시간(시작, 끝)이 담긴 배열이 주어졌을 때, 최소한의 방만으로 운영될려면 최소 몇 개의 방이 필요한지 구하시오. 단, 손님이 한 번 이용한 방은 10분의 청소시간이 필요하다.
[ 예시 ]
| book_time | result |
|---|---|
| [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]] | 3 |
[ 제약 조건 ]
1 ≤ book_time의 길이 ≤ 1,000
book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
[대실 시작 시각, 대실 종료 시각] 형태입니다.
시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
예약 시각이 자정을 넘어가는 경우는 없습니다.
시작 시각은 항상 종료 시각보다 빠릅니다.
[ 프로그래머스 ]
풀이
- Greedy 알고리즘 사용
(1) String 배열로 들어온 대실 시간을 계산하기 쉽게 int로 변환하여 int 배열에 넣는다. 이 때 청소 시간을 미리 고려하고자 대실 종료 시각 + 10분을 계산하고, 만약 60분을 넘어가면 40을 추가로 더하여 +1h가 되도록 한다.
(2) (1)에서 완성된 배열을 대실 시작 시각의 오름차순으로 정렬한다.
(3) 0~객실의수만큼 반복한다.
- 이미 방문한 객실은 건너 뛴다.
- 그렇지 않을 경우, 방문 처리하고 해당 방의 마지막 종료 시각을 해당 인덱스의 종료시각으로 넣는다.
(4) (3)에서 정한 끝 시간 보다 배정되지 않는 방의 시작 시각이 더 크면, 배정 가능한 방임으로
방문처리하고, 해당 방의 종료 시각을 해당 방의 대실 종료 시각으로 대처한다.
(5) rooms의 배열 값이 -1이라는 것은 배정된 적 없는 방임을 나타냄으로 -1일 경우 answer++를 진행한다.
Code
import java.util.*;
class Solution {
public int solution(String[][] book_time) {
int answer = 0;
int room_size = book_time.length;
int[][] list = new int[room_size][2];
int gotRoom = 0;
boolean[] visited = new boolean[room_size];
int[] rooms = new int[room_size];
Arrays.fill(rooms, -1);
for(int i=0;i<room_size;i++) {
int start = Integer.parseInt(book_time[i][0].replace(":",""));
int end = Integer.parseInt(book_time[i][1].replace(":",""));
end += 10;
if (end%100 >= 60) {
end += 40;
}
list[i][0] = start;
list[i][1] = end;
}
Arrays.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0])
return o2[1] - o1[1];
return o1[0] - o2[0];
}
});
for(int i=0;i<room_size;i++) {
if (visited[i])
continue;
visited[i] = true;
rooms[i] = list[i][1];
for(int j=0;j<room_size;j++) {
if (visited[j])
continue;
if (rooms[i] <= list[j][0]) {
visited[j] = true;
rooms[i] = list[j][1];
}
}
}
for(int i : rooms){
if (i != -1) {
answer++;
}
}
return answer;
}
}시도
- 대실 종료 시각을 오름차순으로 정렬 = 테스트 케이스 3개만 통과
: 백준의 회의실 배정처럼 종료 시각을 오름차순으로 정렬하였더니 프로그래머스의 테스트 케이스를 3개밖에 통과하지 못 했다. 게시글에 올라온 반례들은 모두 통과하는데 이유가 무엇일까?
import java.util.*;
class Solution {
public int solution(String[][] book_time) {
int answer = 0;
int room_size = book_time.length;
int[][] list = new int[room_size][2];
int gotRoom = 0;
boolean[] visited = new boolean[room_size];
int[] rooms = new int[room_size];
Arrays.fill(rooms, -1);
for(int i=0;i<room_size;i++) {
int start = Integer.parseInt(book_time[i][0].replace(":",""));
int end = Integer.parseInt(book_time[i][1].replace(":",""));
end += 10;
if (end%100 >= 60) {
end += 40;
}
list[i][0] = start;
list[i][1] = end;
}
Arrays.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1])
return o2[0] - o1[0];
return o1[1] - o2[1];
}
});
for(int i=0;i<room_size;i++) {
if (visited[i])
continue;
visited[i] = true;
rooms[i] = list[i][1];
for(int j=0;j<room_size;j++) {
if (visited[j])
continue;
if (rooms[i] <= list[j][0]) {
visited[j] = true;
rooms[i] = list[j][1];
}
}
}
for(int i : rooms){
if (i != -1) {
answer++;
}
}
return answer;
}
}느낀점
일전에 푼 백준의 회의실 배정 문제와 매우 유사한 문제였다. 지금도 이해는 안 가지만 정렬 기준을 잘 못 정해 계속 틀려 헛우물만 팠다. :(
