(JAVA) [BOJ]백준 11000번 : 강의실 배정

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

11725번: 트리의 부모 찾기

11000, 강의실 배정

이번 문제는 최소 우선순위 큐와 시작 시간과 종료 시간을 저장하는 class 를 생성하여 해결하였다.

 

# Process

Class, Lecture

: 시작시간과 종료시간을 저장하는 Lecture Class 를 생성하였다.

생성자로 두 시간을 저장해주는 간단한 설계이다.

static class Lecture
{
    public int sdate;
    public int edate;

    Lecture(int startDate, int endDate)
    {
        this.sdate = startDate;
        this.edate = endDate;
    }
}

 

Sort

: 우선 시작시간 기준으로 오름차순 정렬해주고, 시작시간이 서로 같다면 종료시간 기준으로 오름차순 정렬해주었다.

// 오름차순 정렬
Arrays.sort(L, 1, N+1, new Comparator<Lecture>() {
    @Override
    public int compare(Lecture o1, Lecture o2) {
        if(o1.sdate == o2.sdate) return o1.edate - o2.edate;
        return o1.sdate - o2.sdate;
    }
});

 

Queue Process

: 맨 첫 강의의 종료시간을 큐에 넣어준다. 순회하면서 종료시간 <= 시작시간의 경우에만 큐를 하나 poll() 해주고 기본적으로 순회한 강의의 종료시간을 넣어준다.

이렇게 되면 이어지는 강의의 경우에는 큐를 빼고 넣고를 반복하며 강의실 개수가 1개임을 의미한다고 생각하면 된다.

 

[1-3], [2-4],[3-5] 의 강의에서 1-3 강의가 큐에 맨 처음 들어가고 순회를 한다고 가정해보자.

종료시간인 3이 큐에 들어가고 [2-4] 강의의 시작 시간인 2는 3<=2 를 만족하지 않기 때문에 큐에서 3을 빼지 않고 4만 큐에 넣어준다. 

그 다음 순회에서 우선순위가 가장 높은 3을 그대로 가져와서 [3-5] 의 강의와 비교했을 때, 3<=3 을 만족하기 때문에 

[1-3] 강의의 종료시간인 3을 큐에서 빼고 [3-5]의 종료시간인 5를 넣어준 후 순회를 마친다.

즉, [1-3] 과 [3-5] 의 강의실과 [2-4]의 강의실 총 2개가 필요함을 알 수 있다.

 

이러한 순회를 마치고 나서 큐의 size 를 출력해주면 된다는 의미이다.

// 우선순위 큐에는 종료 시간만 들어가고, 오름차순으로 자동정렬
q.offer(L[1].edate);

for(int i=2; i<=N; i++)
{
    /*
     * peek() : 우선순위가 가장 높은 값을 참조
     * 종료시간 <= 시작시간의 경우에 직전의 종료시간을 꺼내고 다음 종료시간을 넣고 계속 비교
     */
    if(q.peek() <= L[i].sdate) q.poll();

    // 순회하면서 현재 end 값을 넣어준다.
    q.offer(L[i].edate);
}

System.out.println(q.size());

 

이러한 로직의 전체 코드는 아래와 같다.

static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();

static PriorityQueue<Integer> q = new PriorityQueue<>();
static Lecture[] L;
static int N;

static class Lecture
{
    public int sdate;
    public int edate;

    Lecture(int startDate, int endDate)
    {
        this.sdate = startDate;
        this.edate = endDate;
    }
}

static void input() 
{
    N = scan.nextInt();   
    L = new Lecture[N+1];
    for(int i=1; i<=N; i++) L[i] = new Lecture(scan.nextInt(), scan.nextInt());
}

static void pro() 
{
    // 오름차순 정렬
    Arrays.sort(L, 1, N+1, new Comparator<Lecture>() {
        @Override
        public int compare(Lecture o1, Lecture o2) {
            if(o1.sdate == o2.sdate) return o1.edate - o2.edate;
            return o1.sdate - o2.sdate;
        }
    });

    // 우선순위 큐에는 종료 시간만 들어가고, 오름차순으로 자동정렬
    q.offer(L[1].edate);

    for(int i=2; i<=N; i++)
    {
        /*
         * peek() : 우선순위가 가장 높은 값을 참조
         * 종료시간 <= 시작시간의 경우에 직전의 종료시간을 꺼내고 다음 종료시간을 넣고 계속 비교
         */
        if(q.peek() <= L[i].sdate) q.poll();

        // 순회하면서 현재 end 값을 넣어준다.
        q.offer(L[i].edate);
    }

    System.out.println(q.size());
}

public static void main(String[] args) 
{
    input();
    pro();
}

 

 

 

 

급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다!