[백준/JAVA] 11000번: 강의실 배정

🔺 문제

11000번: 강의실 배정

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, cnt;
    static int[][] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N + 1][2];
        cnt = N;
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr, new Comparator<int[]>() {
           public int compare(int[] o1, int[] o2) {
               if(o1[0] == o2[0])   return o1[1] - o2[1];   // 시작 시간이 같다면, 종료 시간 기준 오름차순 정렬
               return o1[0] - o2[0];                        // 시작 시간 기준 오름차순 정렬
           } 
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();    // 종료 시간 기준 오름차순 정렬
        pq.add(arr[0][1]);
        
        for(int i = 1 ; i <= N - 1 ; i++) {
            if(pq.peek() <= arr[i][0]) // 가장 빨리 끝나는 강의의 종료 시간 vs 배정 안 된 강의의 시작 시간
                pq.poll();
            
            pq.add(arr[i][1]); // 배정이 안 된 강의를 우선순위 큐에 넣음 (= 새로운 강의실에 강의 배정)
        }
        
        System.out.println(pq.size());
    }
}

✅ 해결 아이디어
✔ 그리디 + 우선순위 큐
: pq에 남은 데이터 갯수 = 필요한 강의실 갯수
 1) 입력 데이터를 오름차순으로 정렬 (시작 시간이 같으면, 종료 시간 기준 오름차순 정렬) ⇨ Line 24-29 
 2) 종료 시간 기준 오름차순 정렬 ⇨ Line 31
 3) 배열의 2번째 값부터 순회하며 가장 빨리 끝난 강의의 종료 시간과 배정되지 않은 강의의 시작 시간을 비교한다. 후자의 값이 더 크다면, 해당 강의는 제거한다. 그리고 배정이 안 된 강의의 종료시간을 우선순위 큐에 넣는다.
 4) 우선순위 큐의 크기 = 필요한 강의실 수이다.

🧩 필요 자료구조

○ 버리는 시간 최소로 ▶ 정렬 활용 (시작 시간 기준 정렬)
○ 강의가 들어갈 자리 찾으려면 현재 배정된 강의의 종료 시간과 비교 ▶ 우선순위 큐 사용

 

 

💥 유의사항

• 입력 데이터 크기가 20만이므로 브루트포스하면 시간초과

• 우선순위 큐 ⇨ 시간 복잡도 : O(n log n)

---

🔺 다른 풀이들

- start와 end 변수를 저장하는 Lecture 클래스를 사용하셨고, 정렬할 때 람다식 활용하셨다.

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

Arrays.sort(lectures, (l1, l2) -> l1.start == l2.start ? l1.end - l2.end : l1.start - l2.start);

---

💬 느낀 점

그리디는 주로 정렬된 자료구조를 활용한다....!!

 

1회독	2회독	3회독	4회독	5회독
V	240418

 

 

(+240418 2회독 : 68244KB, 676ms) ✅

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[][] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N][2];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0])  return o1[1] - o2[1];   // 시작 시간이 같다면, 종료 시간 기준 오름차순 정렬
                return o1[0] - o2[0];                       // 시작 시간 기준 오름차순 정렬
            }
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();  // 종료 시간 기준 오름차순 정렬
        pq.add(arr[0][1]);
        
        for(int i = 1 ; i < N ; i++) {
            // 가장 빨리 끝나는 강의의 종료 시간 vs 배정 안 된 강의의 시작 시간
            if(pq.peek() <= arr[i][0])
                pq.poll();
                
            // 배정이 안 된 강의를 우선순위 큐에 넣음
            pq.add(arr[i][1]);
        }
        
        System.out.println(pq.size());  // 우선순위 큐 크기 = 필요한 강의실 수
    }
}
 

---

(참고)

[알고리즘] 백준 11000 강의실 배정 Java

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