[Java] 프로그래머스 - 호텔 대실

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

내 코드

import java.util.*;
class Solution {
    private int answer = 1;
    
    public int solution(String[][] book_time) {
        //0
        int[][] int_book_time = convertStringArrToIntArr(book_time);
        
        //1
        sortByCheckout(int_book_time);
        
        //2. 현재 사용중인 방 배열 추가해서 초기값으로 첫번째 요소 삽입 & answer++;

        List<Integer> occupied = new ArrayList<>();
        occupied.add(int_book_time[0][1]);
        
        //3
        calc(int_book_time, occupied);
        
        //4. return answer        
        return answer;
    }
    //0. String[][] -> int[][]
    private int[][] convertStringArrToIntArr(String[][] book_time){
        int size = book_time.length;
        int[][] int_book_time = new int[size][2];
        
        for(int i=0; i<size; i++){
            String[] checkinSplited = splitTime(book_time[i][0]);
            String[] checkoutSplited = splitTime(book_time[i][1]);
            int_book_time[i][0] = makeIntTime(checkinSplited);
            int_book_time[i][1] = makeIntTime(checkoutSplited);
        }
        
        return int_book_time;
    }
    
    private String[] splitTime(String str){
        String[] arr = str.split(":");
        return arr;
    }
    
    private int makeIntTime(String[] splited){
        StringBuilder sb = new StringBuilder();
        sb.append(splited[0]);
        sb.append(splited[1]);
        return Integer.parseInt(sb.toString());
    }
    //1. 퇴실 시간을 기준으로 정렬
    private void sortByCheckout(int[][] book_time){
        Arrays.sort(book_time, Comparator.comparingInt((int[] o) -> o[1]));
    }
    
//3. 반복문 돌며 사용중인 방 배열 내 요소들의 퇴실시간+10 이 현재 요소의 입실 시간보다 이르거나 같을 경우 해당 요소들 삭제, 
//    현재 요소 append / 없을 경우 append후 answer++
//아니면 현재answer보다 occupied의 size가 작을 때, list에 삽입하고 answer은 카운트 x. 그러나, 이상일 때, 현재 타임과 요소+10들을 비교, 뺄게 잇으면 삭제, 삭제 이후도 answer보다 크면 현재 타임 삽입 및 answer++
    private void calc(int[][] book_time, List<Integer> occupied){
        for(int i=1; i<book_time.length; i++){
        // System.out.println("occupied: "+occupied);
            if(occupied.isEmpty()){
                occupied.add(book_time[i][1]);
                continue;
            }
            
            boolean flag=false;
            for(int j=0; j<occupied.size(); j++){
                if(occupied.get(j) + 10 <= book_time[i][0]){
                    occupied.remove(j);
                    flag=true;
                }
            }
            if(!flag){
                answer++;
            }
            occupied.add(book_time[i][1]);
        }
        // System.out.println("final occupied: "+occupied);
        
    }
    
}

//퇴실 후 10분까지 같은 방 사용 불가

정답 코드1

import java.util.*;

class Solution {
    public int solution(String[][] book_time) {
        int answer = 0;
        //1.
        int[][] book_time_int = toIntArr(book_time);
        //2.
        sortBookTime(book_time_int);
        //3.
        answer=calcMinRoom(book_time_int);
        return answer;
    }

    //1. StringArr -> intArr. 이 때 퇴실시간 +10해서 저장하되, 더한 값이 60분 이상이라면, +100 -60
    private int[][] toIntArr(String[][] arr){
        int size = arr.length;
        int[][] newArr = new int[size][2];

        for(int i=0; i<size; i++){
            newArr[i][0] = Integer.parseInt(arr[i][0].replace(":",""));
            newArr[i][1] = Integer.parseInt(arr[i][1].replace(":",""))+10;
            if(newArr[i][1]%100>=60){
                newArr[i][1]+=(100-60);
            }
        }

        return newArr;
    }   

    //2. 입실시간 기준 오름차순 정렬. 이 때, 두 요소의 입실시간이 같다면 다음 기준은 퇴실시간으로.
    private void sortBookTime(int[][] arr){
        Arrays.sort(arr, (a,b)->{
            if(a[0] > b[0]){
                return 1;
            } 
            else if(a[0]<b[0]){
              return -1;  
            } 
            else{
                if(a[1]>b[1]){
                    return 1;
                }else{
                    return -1;
                }
            }
        });
    }

    //3. PriorityQueue사용, 요소는 퇴실시간+10으로 한다. 모든 예약타임을 pq의 peek와 비교하며 현재 입실시간이 peek보다 크거나 같다면 pq.poll() 및 add/ 반대라면 only add
    private int calcMinRoom(int[][] arr){
        PriorityQueue<Integer> occupied = new PriorityQueue<>();
        for(int[] time : arr){
            if(occupied.size()==0){
                occupied.add(time[1]);
                continue;
            }
            int earliestCheckout=occupied.peek();
            if(time[0] >= earliestCheckout){
                occupied.poll();
            }
            occupied.add(time[1]);
        }
        return occupied.size();
    }

}

• String[][]을 int[][]로 변환하기 위해 replace() 메서드 활용
• 시간 단위 유지하기 위해 60분 초과 시 +100분 -40분 연산
• 변환한 int[][]을 정렬. 이 때 각 요소의 첫번째 요소 즉, 입실 시간을 기준으로 오름차순 정렬하되 입실 시간이 같을 경우 퇴실시간이 빠른 순으로 정렬. Array.sort()의 매개변수로 람다식 삽입하여 구현 가능.
• PriorityQueue사용. 요소로 퇴실시간이 들어가며 다음 입실시간과 pq의 peek비교, 입실시간이 peek보다 늦으면 poll.

 

 

정답 코드2

import java.util.*;

class Solution {
    class Book{
        public Book(int start_time, int end_time) {
            this.start_time = start_time;
            this.end_time = end_time;
        }

        int start_time,end_time;
    }

    List<Book> bookList=new ArrayList<>();
    int toMinute(String time){
        StringTokenizer stk=new StringTokenizer(time,":");
        int hour=Integer.parseInt(stk.nextToken());
        int minute=Integer.parseInt(stk.nextToken());
        return hour*60+minute;
    }

    public int solution(String[][] book_times) {
        for(String[] book_time:book_times){
            int start_time=toMinute(book_time[0]);
            int end_time=toMinute(book_time[1]);

            bookList.add(new Book(start_time,end_time));
        }
        // 시작 시간대로 정렬
        Collections.sort(bookList,(o1,o2)->{
            if(o1.start_time==o2.start_time) return o1.end_time-o2.end_time;
            else return o1.start_time-o2.start_time;
        });

        // 리스트를 방문하며 몇개가 필요할지 체크
        List<Integer> endTimeList=new ArrayList<>();

        for(Book book:bookList){
            boolean isOk=false;
            for(int i=0;i<endTimeList.size();i++){
                // 정리시간 10분
                int endTime=endTimeList.get(i)+10;
                // check
                if(book.start_time>=endTime) {
                    // 예약 시간 넣고 업데이트
                    endTimeList.set(i,book.end_time);
                    isOk=true;
                    break;
                }
            }
            // 아무 방도 넣지 못하면 새로운 방 추가
            if(!isOk) endTimeList.add(book.end_time);
        }

        return endTimeList.size();
    }
}

• 예약시간의 입실시간과 퇴실시간을 필드로 갖는 내부 클래스 Book 선언
• 문자열로 주어진 시, 분을 분 단위로 통일하기 위한 toMinute메서드 정의
• 주어진 String[][]을 돌며 StringTokenizer사용하여 입실 시간과 퇴실시간을 Book객체에 대입, BookList에 add
• bookList 입실시간 순으로 sort. 이 때 Collections.sort()사용하는데 입실시간이 같으면 퇴실시간으로 정렬하기 위해 람다식 매개변수 사용.
  정렬된 bookList돌며 조건에 부합하는 경우 endTimeList에 현재요소 add
• endTimeList의 최종 size반환

 

새로 알게된 사실

Arrays.sort(), Collections.sort() 사용 시 람다식 사용해서 세부 정렬 방법 정의. 해당 람다식은 함수형 인터페이스 Comparator를 구현한 익명 구현 객체이다. 

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Comparator.html

참고 블로그: https://ifuwanna.tistory.com/328

 

split과 StringBuilder사용해 복잡하게 구현하는 대신 replace혹은 StringTokenizer를 사용하자

참고 블로그: https://123okk2.tistory.com/427

 

자료구조 문제가 아니더라도 다양한 Collection자료구조 사용하면 쉽게 해결가능하더라.. 연습을 통해 여러 자료구조에 대해 더 자세히 알아서 새로운 문제 풀 때 떠올릴 수 있도록 하자.

 

그리고 내부 클래스를 사용하는 아이디어도 한번쯤 떠올려 보자.