99클럽 코테 스터디 19일차 TIL

백준 - 1374번

풀이

1번 강의실에 가장 처음으로 시작하는 A 강의를 넣고, A 강의 종료 시간과 다른 강의 시작시간을 비교한다.

B 강의 시작시간이 더 크다면 A 강의를 삭제하고, B 강의를 넣는다.

모든 강의가 진행될 때까지 위 과정을 반복한다.

 

구현

import java.io.*;
import java.util.*;

public class Main {

    static Queue<Lecture> lectures = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            lectures.add(new Lecture(num, start, end));
        }

        Queue<Integer> rooms = new PriorityQueue<>(); // 강의실
        rooms.add(lectures.remove().end); // 가장 처음 시작하는 강의 종료시간 추가

        while (!lectures.isEmpty()) {
            int size = rooms.size();
            Lecture lecture = lectures.remove(); // 다음 강의
            boolean isEmpty = false;

            for (int i = 0; i < size; i++) {
                if (rooms.peek() <= lecture.start) {
                    rooms.remove(); // 기존 강의 삭제
                    isEmpty = true;
                    rooms.add(lecture.end); // 다음 강의 종료시간 추가
                    break;
                }
            }
            
            // 강의실이 계속 사용 중인 경우 새로운 강의실 추가
            if (!isEmpty) rooms.add(lecture.end);
        }

        System.out.println(rooms.size());
        br.close();
    }
    
    // 강의 시작 시간 기준 정렬 
    static class Lecture implements Comparable<Lecture> {
        int num;
        int start;
        int end;

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

        @Override
        public int compareTo(Lecture o) {
            if (this.start == o.start) {
                return this.end - o.end;
            }
            return this.start - o.start;
        }
    }
}

---

PriorityQueue

우선순위 큐는 요소들이 우선순위에 따라 정렬되는 큐 자료구조이다.

일반적인 큐가 FIFO 원칙으로 처리되는 반면, 우선순위 큐는 이름처럼 우선순위가 높은 요소를 먼저 처리한다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(5);
        pq.add(1);
        pq.add(3);

        // 요소를 오름차순으로 정렬하여 출력
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 출력 순서: 1, 3, 5
        }
    }
}

Java의 우선순위 큐는 내부적으로 최소 힙(min heap) 구조를 사용해서 가장 작은 요소가 먼저 나오도록 구현되어 있다.

그렇기 때문에 우선순위 큐는 기본적으로 오름차순으로 정렬된다.

 

문제에서는 강의 시작 시간을 기준으로 정렬해야 했기 때문에 Comparble을 구현하여 정렬 기준을 직접 설정했다.

---

백준 1374번 - 강의실

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

 

참고

https://velog.io/@taebong1012/%EB%B0%B1%EC%A4%80-1374%EB%B2%88-%EA%B0%95%EC%9D%98%EC%8B%A4-JAVA