문제

프로그래머스 연습문제이다.
생각없이 제출해보니 첫제출이었다. 이런건 또 처음이네.

예약 시간이 주어질때 겹치지 않기위해 최소 몇개의 방이 필요할지 묻는 문제다.

<부르트포스>
예약 시간(book time)이 1000개까지 들어오니까
1000개를 정렬해보면 된다.
(1000! x 999! x 998! ...)

정확한 빅오를 계산하진 못하겠지만 1억은 쉽게 넘어간다. (불가능)

---

<그리디>
그래서 예시 그림처럼 시작 시간대로 정렬 후
앞에서부터 꽉꽉 채워넣기로 했다.

문제는 시간복잡도인데
입력이 10^3이고
시작 시간대로 정렬을 해야하니까 NlogN 이어서 괜찮고

새로운 예약을 체크할때마다 기존 예약을 전체 순회해서
N^2 이 걸려서 10^6으로 이것도 통과다.

---

이번 문제에서 핵심이 되는 코드인데

시작 시간대로 예약을 정렬한 후
종료 시간만 따로 저장하는 리스트를 만들어
앞시간부터 예약을 넣어준다.

그리고 예약을 넣을 수 있다면 기존 예약 시간을 업데이트해주고
각 반복마다 end_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;
            // end_time 기준으로 정렬
            Collections.sort(endTimeList);
            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);
        }

근데 각 반복마다 예약시간을 정렬해주지 않아도 AC 가 나오긴한다.
(그러면 안될거같은데)

내 코드

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;
            // end_time 기준으로 정렬
            Collections.sort(endTimeList);
            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();
    }
}