[백준] 1931 회의실 배정 java 풀이

1. 문제 설명 📌

문제 링크

문제 설명이 직관적이라 추가 설명 생략

2. 접근 방식 🗃️

KEY WORD: GREEDY ALGORITHM

(1) 회의의 시작 시간과 끝 시간을 묶어서 하나의 객체로 만들기. 또 이 객체들을 ArrayList로 묶기

(2) 회의를 끝 시간이 빠른 순으로 정렬 (끝 시간이 같다면 시작 시간이 빠른 순으로 정렬)

(3) int prev_end_time 초기값: ArrayList.get(0)의 끝시간

(4) ArrayList를 순회하며 prev_end_time <= now.startTime인 경우 ans_cnt +1 올리고, prev_end_time = now.endTime으로 경신

(1) Greedy Algorithm 인 것은 어떻게 알았니? 🤔

결론: 회의를 끝 시간 순으로 정렬 했을 때, 순서가 [meeting A, meeting B, meeting C, ...] 순으로 되어 있을 때, meeting A와 meeting C를 배정할 수 없다면, meeting B로도 meeting C를 배정할 수 없다. 반면 A와 C가 연달아 배정이 가능하다면 B와 C도 연달아 배정할 수 있는 가능성이 있다. 어쩌면 A ➜ B ➜ C 도 가능하다. 따라서 맨 처음 값부터 최대한 많이 고르는 것이 손해를 보지 않기 때문에 Greedy Algorithm이 된다.

A를 고르면 A ➜ B ➜ C도 가능해지고, 안되면 A ➜ C를 고르면 된다. 반면 A ➜ B가 안된다고 바로 B 부터 시작해버리면 고를 수 있는 개수가 B ➜ C로 제한된다.

3. 코드 소개 🔎

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        int ans = 1;
        int prev_end_time = 0;
        int N;
        Meeting [] meetings;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        meetings = new Meeting[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            meetings[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(meetings, (o1,o2) -> {
            if(o1.e == o2.e) return o1.s - o2.s;
            return o1.e - o2.e;
        });
        prev_end_time = meetings[0].e;

        for (int i = 1; i < N; i++) {
            Meeting now = meetings[i];
            if(prev_end_time <= now.s) {
                ans++;
                prev_end_time = now.e;
            }
        }
        System.out.println(ans);
    }
}

class Meeting {
    int s;
    int e;

    public Meeting(int s, int e){
        this.s = s;
        this.e = e;
    }

    public String toString() {
        return s+ " ~ " + e;

    }
}

4. 배운 것들 🎯

(1) 반례 처리

끝 시간이 같을 경우, 시작 시간이 빠른 순으로 정렬해야, 모든 경우의 수를 탐독할 수 있다.

반례

3
4 4
1 4
5 6

끝 시간 같을 때, 시작 시간 오름 차순 안해주면 2개밖에 못 고름. 답은 3개 다 고르는 것임.