작성 코드
import java.io.*;
import java.util.*;
public class Classroom_assignment_11000 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
List<int[]> times = new ArrayList<>();
for (int i = 0; i < n; i++) {
int[] input = new int[2];
st = new StringTokenizer(br.readLine());
input[0] = Integer.parseInt(st.nextToken());
input[1] = Integer.parseInt(st.nextToken());
times.add(input);
}
times.sort(Comparator.comparingInt(a -> a[0]));
int cnt = 0;
PriorityQueue<Integer> end_times = new PriorityQueue<>();
for (int[] time : times) {
int start = time[0];
int end = time[1];
if (!end_times.isEmpty() && end_times.peek() <= start) {
end_times.poll();
}
end_times.offer(end);
cnt = Math.max(cnt, end_times.size());
}
System.out.println(cnt);
}
}설명(자바)
이 코드는 입력으로 강의 시간을 받아서 최대한 많은 수의 강의를 할 수 있는 경우의 수를 계산하는 프로그램입니다. 이 프로그램은 자바로 작성되어 있습니다.
프로그램의 로직은 다음과 같습니다:
- 먼저,
BufferedReader와StringTokenizer를 사용하여 입력을 받습니다.BufferedReader는 입력을 효율적으로 처리하기 위해 사용되는 클래스이고,StringTokenizer는 문자열을 특정 구분자를 기준으로 나누는 데 사용됩니다. - 다음으로, 첫 번째 입력값인
n을 읽어들입니다. 이 값은강의의 개수를 나타냅니다. List<int[]> times를 생성합니다. 이 리스트는 각각의 강의 시간을 저장할 배열(int[])의 리스트입니다.n번 반복하면서 강의의시작 시간과종료 시간을 입력 받고, 이를int 배열로 만들어times리스트에 추가합니다.times리스트를 강의 시작 시간을 기준으로 오름차순으로 정렬합니다. 이를 위해times.sort()를 사용하며,Comparator.comparingInt(a -> a[0])를 사용하여 배열의 첫 번째 값을 기준으로 정렬합니다.cnt변수를0으로 초기화하고,PriorityQueue인end_times를 생성합니다.PriorityQueue는 원소들을 우선순위에 따라 정렬하여 저장하는 자료구조입니다. 이 경우,end_times는 종료 시간을 기준으로 정렬되어야 합니다.times리스트를 반복하면서 각각의 강의에 대해 다음을 수행합니다:- 현재 강의의 시작 시간(
start)과 종료 시간(end)을 변수에 저장합니다. end_times가 비어있지 않고,end_times의 가장 작은 값(즉, 가장 빨리 끝나는 강의의 종료 시간)이 현재 강의의 시작 시간보다 작거나 같으면, 해당 강의는 이미 끝난 강의이므로end_times에서제거합니다(end_times.poll()).- 현재 강의의 종료 시간을
end_times에 추가합니다(end_times.offer(end)). cnt값을end_times의 크기와 비교하여 갱신합니다.cnt는 현재까지의 최대 강의 수를 나타냅니다.
- 현재 강의의 시작 시간(
cnt값을 출력합니다.
따라서, 이 프로그램은 강의의 시작 시간과 종료 시간을 입력받아 최대한 많은 수의 강의를 할 수 있는 경우의 수를 출력합니다. 이를 위해 종료 시간을 기준으로 정렬된 우선순위 큐를 사용하고, 반복문을 통해 각각의 강의에 대해 시작 시간과 종료 시간을 비교합니다.
자바스크립트
class Node {
constructor(val, priority) {
this.val = val;
this.priority = priority;
}
}
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(val, priority) {
let newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
dequeue() {
const min = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.bubbleDown();
}
return min;
}
bubbleUp() {
let idx = this.values.length - 1;
const element = this.values[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
let parent = this.values[parentIdx];
if (element.priority >= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
bubbleDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
if (leftChild.priority < element.priority) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
if (
(swap === null && rightChild.priority < element.priority) ||
(swap !== null && rightChild.priority < leftChild.priority)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}
const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const n = +input.shift();
const arr = input.map(el=>el.split(' ').map(el=>+el));
arr.sort((a,b)=> a[0] - b[0])
const pq = new PriorityQueue();
pq.enqueue(arr[0], arr[0][1]);
for(let i = 1 ; i < n; i++) {
const value = pq.dequeue().val;
if(arr[i][0] < value[1]) {
pq.enqueue(value, value[1]);
}
pq.enqueue(arr[i], arr[i][1]);
}
console.log(pq.values.length);설명(자바스크립트)
이 코드는 우선순위 큐(Priority Queue)를 사용하여 강의 시간을 처리하는 프로그램입니다. 이 코드는 JavaScript로 작성되어 있습니다.
- 먼저,
Node클래스를 정의합니다. Node 클래스는 강의 시간과 우선순위를 가지는 노드를 나타냅니다. 이 클래스는val과priority라는 두 개의 속성을 가지며, 생성자에서 이 속성들을 초기화합니다. - 다음으로,
PriorityQueue클래스를 정의합니다.PriorityQueue클래스는 우선순위 큐를 구현하는데 사용됩니다. 이 클래스는values라는 배열을 가지며, 생성자에서 이 배열을 초기화합니다. enqueue메서드를 구현합니다. 이 메서드는 새로운 노드를 큐에 추가하고, 추가된 노드를 올바른 위치로 이동시킵니다. 먼저, 새로운 노드를 생성하고 큐의 끝에 추가합니다. 그리고bubbleUp메서드를 호출하여 새로운 노드를 올바른 위치로 이동시킵니다.dequeue메서드를 구현합니다. 이 메서드는 큐에서 우선순위가 가장 높은 노드를 제거하고 반환합니다. 먼저, 큐의 맨 앞에 있는 노드를 min 변수에 저장합니다. 그리고 큐의 마지막 노드를 가져와서 맨 앞으로 이동시킵니다. 이후 bubbleDown 메서드를 호출하여 노드를 올바른 위치로 이동시킵니다. 마지막으로, min 변수에 저장된 우선순위가 가장 높은 노드를 반환합니다.bubbleUp메서드를 구현합니다. 이 메서드는 새로운 노드를 올바른 위치로 이동시키는 역할을 합니다. 새로운 노드를 맨 끝에서 시작하여 부모 노드와 비교하고, 우선순위가 더 높은 경우에는 부모 노드와 위치를 교환합니다. 이 과정을 루트 노드에 도달하거나 우선순위가 더 낮은 경우까지 반복합니다.bubbleDown메서드를 구현합니다. 이 메서드는 노드를 올바른 위치로 이동시키는 역할을 합니다. 먼저, 루트 노드에서 시작하여 왼쪽 자식 노드와 오른쪽 자식 노드 중 우선순위가 더 높은 노드를 찾습니다. 그리고 현재 노드와 우선순위가 더 높은 자식 노드를 비교하여 위치를 교환합니다. 이 과정을 자식 노드가 없거나 현재 노드의 우선순위가 자식 노드의 우선순위보다 높은 경우까지 반복합니다.- 프로그램의 나머지 부분은 입력을 처리하고 우선순위 큐를 사용하여 강의 시간을 처리하는 부분입니다. 먼저, 입력을 읽어들이고 배열로 변환합니다. 그리고 배열을 강의 시작 시간을 기준으로 오름차순으로 정렬합니다.
PriorityQueue클래스의 인스턴스를 생성합니다.- 첫 번째 강의를 우선순위 큐에 추가합니다. 이때, 강의의 종료 시간을 우선순위로 사용합니다.
- 반복문을 사용하여 나머지 강의에 대해 다음을 수행합니다:
- 큐에서 가장 우선순위가 높은 강의를 가져옵니다.
- 현재 강의의 시작 시간과 가져온 강의의 종료 시간을 비교합니다.
- 현재 강의의 시작 시간이 가져온 강의의 종료 시간보다 작으면, 현재 강의를 큐에 다시 추가합니다.
- 현재 강의를 큐에 추가합니다.
- 최종적으로 큐의 길이를 출력합니다. 이 값은 최대로 할 수 있는 강의 수를 나타냅니다.
따라서, 이 프로그램은 우선순위 큐를 사용하여 강의 시간을 처리하고, 시작 시간과 종료 시간을 비교하여 최대로 할 수 있는 강의 수를 출력합니다.
파이썬
import heapq
n = int(input())
times = []
for _ in range(n):
st, en = map(int, input().split())
times.append((st, en))
times.sort(key=lambda x: x[0])
cnt = 0
end_times = []
for st, en in times:
if end_times and end_times[0] <= st:
heapq.heappop(end_times)
heapq.heappush(end_times, en)
cnt = max(cnt, len(end_times))
print(cnt)
필요하다면 공부하는 개발자, 한승준