프로그래머스 | LV.2 호텔 대실 - 구현 문풀 (Java)

⬛ 프로그래머스 | LV.2 호텔 대실 - 구현 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

1) Room 클래스 선언하여 st 기준 오름차순 우선 정렬하도록 정의한다.

2) 정렬된 RoomList 에서 visited로 체크하면서 매번 현재 room의 ed + 10 보다 st시간이 크거나 같은 room을 발견할 때마다 visit 체크 후 갱신해주면서 처리하면 된다.

3) 이럴 경우 answer는 해당 룸에서 처리 가능한 애들 묶음만 ++ 처리 하므로 정답을 리턴한다.

---

1차 시도 | 예제 통과 최종 실패

처음 풀 때는 ed 시간 기준 오름차순 정렬을 우선하고, ed 시간이 같은 경우 st 를 오름차순 정렬하도록 조건을 짰었다.

매번 빨리 끝나는 ed 시간을 우선으로 한다면 해당 ed+10 뒤로 오는 st 예약건을 처리하는 것이 더 밀집되게 최소방을 쓸 수 있을 거라고 생각했기 때문인데, 처리는 ed 기준으로 하더라도 정렬 자체는 st 기준 오름차순으로 두는 것이 가장 밀집된 처리를 위해 좋았다. 

끝 시간 기준 오름차순 정렬 시, 문제가 요구했던 최소한의 객식을 사용하라는 말에 어긋나는 반례가 존재한다.

[["05:00", "15:00"], ["10:00", "20:00"], ["20:30", "23:00"], ["15:30", "23:30"]] 

→ 이 케이스가 2개가 나와야 맞는데, 내가 정의한대로 정렬하면 3개가 나온다. 

왼쪽이 ed 시간 오름차순 정렬이고, 오른쪽이 st 시간 오름차순 정렬이다. 더 밀집된 처리를 위해 바꿔야겠다는 생각이 들었다. 

ed 기준 오름차순 우선 시 반례

import java.util.*;
class Room implements Comparable<Room>{
    int st, ed;
    Room(int st, int ed){
        this.st = st;
        this.ed= ed;
    }
    @Override
    public int compareTo(Room o){
        if(this.ed == o.ed) return this.st - o.st;
        return this.ed - o.ed;//기본 끝 시간 오름차순 정렬 
    }
}
class Solution {
    //getTime
    public static int getTime(String time){
        int H = Integer.parseInt(time.split(":")[0]);
        int M = Integer.parseInt(time.split(":")[1]);
        
        return 60 * H + M;
    }
    
    //솔루션 함수 
    public int solution(String[][] book_time) {
        int answer = 0;
        int N = book_time.length;//방 개수 
        List<Room> roomList = new ArrayList<>();
  
        for(String[] tmp : book_time){
            int st = getTime(tmp[0]);
            int ed= getTime(tmp[1]);
            roomList.add(new Room(st, ed));
        }
        //ed 시간 오름차순 정렬
        Collections.sort(roomList);
        
        boolean[] visited= new boolean[N];
        for(int i=0; i<roomList.size(); i++){
            Room cur = roomList.get(i);
            if(visited[i]) continue;
            visited[i] = true;
            answer++;
            
            for(int j=i+1; j<roomList.size(); j++){
                if(cur.ed + 10 <= roomList.get(j).st){
                    visited[j] = true;
                    cur = roomList.get(j);
                }
            }
        }

        return answer;
    }
}

 

2차 시도 | st 기준 오름차순 정렬 우선하도록 변경

결국 st 시간이 다르지 않다면 st 기준 오름차순 정렬해야 더 빼곡하게 최소 객실 수를 사용하여 예약손님을 받을 수 있는 것이다.

💚 제출 코드

import java.util.*;
class Room implements Comparable<Room>{
    int st, ed;
    Room(int st, int ed){
        this.st = st;
        this.ed = ed;
    }
    public int compareTo(Room o){
        if(this.st == o.st) return this.ed - o.ed;//시작값 같으면 e 오름차순
        return this.st-o.st;//기본 시작 시간 오름차순 정렬 
    }
}
class Solution {
    public int getTime(String x){
        int H = Integer.parseInt(x.split(":")[0]);
        int M = Integer.parseInt(x.split(":")[1]);
        return 60 * H + M;
    }
    //솔루션 함수 
    public int solution(String[][] book_time) {
        int answer = 0;
        
        List<Room> roomList = new ArrayList<>();
        for(String[] x : book_time){
            int st = getTime(x[0]);
            int ed = getTime(x[1]);
            roomList.add(new Room(st, ed));
        }
        
        Collections.sort(roomList);
        boolean[] visited= new boolean[book_time.length];
        //시작시간 오름차순 기준 
        for(int i=0; i<roomList.size(); i++){
            if(visited[i]) continue;
            Room target = roomList.get(i);
            visited[i] =true;
            answer++;
            for(int j=i+1; j<roomList.size(); j++){
                if(!visited[j] && roomList.get(j).st >= target.ed + 10){
                    visited[j] = true;
                    target = roomList.get(j);
                }
            }
        }
        
        return answer;
    }
    
}