[백준] 1931번 회의실 배정(java)

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

이 문제는 그리디 카테고리에 있는 문제이다.

 

핵심

이 문제의 핵심은 어떻게 배정을 해야 많은 사람이 이용할 수 있을까?이다.

끝나는 시간이 빠른 순서대로 정렬을 하고 그에 맞게 회의실에 넣어주면 된다.

코드를 보면 쉽게 이해할 수 있다.

 

 

정답 코드

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List<Conference> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            Conference conference = new Conference(sc.nextInt(), sc.nextInt());
            list.add(conference);
        }
        list.sort(new Comparator<Conference>() {
            @Override
            public int compare(Conference o1, Conference o2) {
                if (o1.getEnd() != o2.getEnd()) {
                    return o1.getEnd() - o2.getEnd();
                } else {
                    return o1.getStart() - o2.getStart();
                }
            }
        });
        int count = 0;
        int endTime = -1;
        for (int i = 0; i < N; i++){
            if (list.get(i).getStart()>=endTime) {
                endTime = list.get(i).getEnd();
                count++;
            }
        }
        System.out.println(count);
    }
}

class Conference {
    private int start;
    private int end;

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    public Conference(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

해설

가장 중요한 포인트는 끝나는 시간이 빠른 순서대로 정렬이 돼야 한다는 것이다.

Conference라는 클래스를 만든 이유는 이러한 방식이 더 편하다고 생각되기 때문이다.

이제 앞서 말한 대로 끝나는 시간이 빠른 순으로 정렬을 한다. 만약 값이 같다면 시작시간이 빠른 순으로 정렬한다.

시작 시간이 이전에 끝난 시간보다 늦거나 같다면 그 회의를 참여시킨다.

 

 

배운 점

이전에 이와 비슷한 문제를 풀어본 적이 있어서 쉽게 풀 수 있었다.

처음에는 이중배열을 사용할까 고민하였지만, 클래스를 한 개 더 만드는 것이 직관이라 생각하였고,

스스로도 이러한 방법이 더 편해서 위와 같은 코드가 나왔다.