[프로그래머스] 호텔 대실(Java), 2차원 배열 정렬

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

---

문제 풀이

먼저 이차원 배열 book_time을 String -> int 로 형 변환을 해준다.

청소 시간이 10분 이므로, 체크아웃 시간에 + 10분을 함께 계산해준 후 book_time을 오름차순으로 정렬한다.

 

각 객실의 최대 퇴실 시간을 저장해주는 maxList를 하나 생성하고, 첫번째 손님의 체크아웃 시간을 넣어준다.

for문으로 book_time 배열과 maxList 를 함께 돌며,

 

1) 다음 차례 손님 A의 체크인 시간이 maxList의 시간들보다 나중일 경우, maxList의 값을 손님 A의 체크아웃 시간으로 치환해준다.

 -> 손님 A가 해당 방으로 들어감

2) 다음 차례 손님 A의 체크인 시간이 maxList의 시간들보다 먼저일 경우, maxList에 손님 A의 체크아웃 시간을 더해준다.

 -> 손님 A에게 다른 방을 내어줌

 

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 1;
        int[][] newBookTime = new int[book_time.length][2];
        
        for(int i=0; i<book_time.length; i++) {
            String startTime = book_time[i][0].replaceAll(":", "");
            String endTime = book_time[i][1].replaceAll(":", "");
            
            newBookTime[i][0] = Integer.parseInt(startTime);
            
            // 청소시간 계산
            int newEndTime = Integer.parseInt(endTime);
            newEndTime += 10;
            
            // 잘못된 부분!!
            if(Integer.parseInt(endTime) % 100 >= 60) {
	            newEndTime = Integer.parseInt(endTime) + 40;
            }
            newBookTime[i][1] = newEndTime;
        }
        
        // 2차원 배열 오름차순 정렬
        Arrays.sort(newBookTime, (o1, o2) -> o1[0] - o2[0]);
        
        ArrayList<Integer> maxList = new ArrayList<>();
        maxList.add(newBookTime[0][1]);
        
        for(int i=1; i<newBookTime.length; i++) {
            Collections.sort(maxList);
            int endTime = newBookTime[i][1];
            int startTime = newBookTime[i][0];
            
            boolean flag = false;
            
            for(int j=0; j<maxList.size(); j++) {
                if(maxList.get(j) <= startTime) { 
                    maxList.set(j, endTime);
                    break;
                } else {
                    flag = true;
                }
            }
            
            if(flag) {
                maxList.add(endTime);
                answer++;
            }
            
        }
        
        return answer;
    }
}

 

-> 위 코드로는 테스트 케이스 9번, 17번 실패

 

위 테스트 케이스가 실패했던 이유를 찾았다.

청소시간을 계산하는 과정에서, 10분을 더한 값을 가지고 아래의 계산을 수행했어야 하는데, 10분을 더하기 전의 값을 가지고 수행했던 것..

 

체크아웃 시간이 12:50 으로 들어온 경우, 이를 int로 바꾸고 +10을 해주면 1260이 되어버린다.

1250을 100으로 나누면 나머지가 60이다. 이 값에 + 40을 하면 1300을 얻을 수 있다.

 

최종 코드는 다음과 같다.

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 1;
        int[][] newBookTime = new int[book_time.length][2];
        
        for(int i=0; i<book_time.length; i++) {
            String startTime = book_time[i][0].replaceAll(":", "");
            String endTime = book_time[i][1].replaceAll(":", "");
            
            newBookTime[i][0] = Integer.parseInt(startTime);
            int newEndTime = Integer.parseInt(endTime);
            
            // 청소시간 계산
            int newEndTime = Integer.parseInt(endTime);
            newEndTime += 10;
            if(newEndTime % 100 >= 60) {
	            newEndTime = newEndTime + 40;
            }
            newBookTime[i][1] = newEndTime;
        }
        
        // 2차원 배열 오름차순 정렬
        Arrays.sort(newBookTime, (o1, o2) -> o1[0] - o2[0]);
        
        ArrayList<Integer> maxList = new ArrayList<>();
        maxList.add(newBookTime[0][1]);
        
        for(int i=1; i<newBookTime.length; i++) {
            Collections.sort(maxList);
            int endTime = newBookTime[i][1];
            int startTime = newBookTime[i][0];
            
            boolean flag = false;
            
            for(int j=0; j<maxList.size(); j++) {
                if(maxList.get(j) <= startTime) { 
                    maxList.set(j, endTime);
                    break;
                } else {
                    flag = true;
                }
            }
            
            if(flag) {
                maxList.add(endTime);
                answer++;
            }
            
        }
        
        return answer;
    }
}

 

---

2차원 배열 정렬 방법 : Comparator 사용하기

Comparator는 비교를 위한 인터페이스로, 인터페이스를 오버라이딩해 원하는 대로 구현이 가능하다.

-> 내림차순 정렬, 다차원 배열 정렬 등

 

Comparator 인터페이스에는 많은 메소드들이 선언되어 있는데 실제 오버라이딩할 함수는 int compare(Object o1, Object o2) 이다.

 

compare 함수는 두 매개변수를 인자로 받아 두 인자를 비교한다.

 

1. 첫 번째 인자가 더 크면 양수를 리턴

2. 동일하면 0을 리턴

3. 두 번째 인자가 더 크면 음수를 리턴

 

// 2차월 배열 오름차순 정렬 : 0번쨰 열 다음 1번째 열 비교
Arrays.sort(arr, new Comparator<int[]>() {
	@Override
    public int compare(int[] o1, int[] o2) {
    	if(o1[0] == o2[0]) {
        	return o1[1] - o2[1];
        } else {
        	return o1[0] - o2[0]; 
        }
    }
});

// 2차월 배열 내림차순 정렬 : 0번쨰 열 다음 1번째 열 비교
Arrays.sort(arr, new Comparator<int[]>() {
	@Override
    public int compare(int[] o1, int[] o2) {
    	if(o1[0] == o2[0]) {
        	return o2[1] - o1[1];
        } else {
        	return o2[0] - o1[0]; 
        }
    }
});