답안

1. 문제 파악 2. 풀이


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
  public static void main(String[] args) {
		int N = 6;
		int[][] reading = {{1, 3}, {2, 5}, {7, 8}, {4, 12}, {9, 10}, {7, 11}}; 
		int[] answer = solution(N, reading);

		System.out.println(answer[0] + " " + answer[1]);
	}
	
	public static int[] solution(int N, int[][] reading) {
		int[] answer = new int[2];

		// 하루에 최대 몇 명이 책을 읽을 수 있는지 구함
		Arrays.sort(reading, new Comparator<int[]>() {
			@Override
			public int compare(int[] start, int[] end) {
				if(start[1] == end[1]){
					return Integer.compare(start[0], end[0]);
				}
				return Integer.compare(start[1], end[1]);
			}
		});

		int cnt = 0;    
		int end = -1;   
		for (int i = 0; i < N; i++) {
			if (reading[i][0] >= end) {
				end = reading[i][1];    
				cnt++;
			}
		}
		answer[0] = cnt;

		// 모든 사람들이 책을 읽기 위해 빌려야 하는 최소 대출 권수
		Arrays.sort(reading, new Comparator<int[]>() {
			@Override
			public int compare(int[] start, int[] end) {
				if(start[0] == end[0]){
					return Integer.compare(start[1], end[1]);
				}
				return Integer.compare(start[0], end[0]);
			}
	   });
        
	  PriorityQueue<Integer> pq = new PriorityQueue<>();
 
    for (int i = 0; i < N; i++) {
      if (!pq.isEmpty() && pq.peek() <= reading[i][0]){
           pq.poll();
      }
      pq.add(reading[i][1]);
	  }
 
		answer[1] = pq.size();
		return answer;
	}
}

1. 문제 파악

하루에 책을 읽을 수 있는 학생의 수와 모든 학생이 책을 읽기 위해서 필요한 책의 수를 구하기 위해서 책을 읽기 시작하는 시점과 종료하는 시점에 따른 정렬이 필요합니다.

하나의 열이 정렬될 때 다른 열도 함께 변동돼야 하기 때문에 Comparator를 활용합니다.

한 명의 학생이 책을 다 읽으면 다른 학생이 책을 읽을 수 있도록 우선순위 큐를 활용합니다.

2. 풀이

책은 한 권만 주어지기 때문에 한 명의 학생이 책을 다 읽었을 때 다른 학생이 책을 읽을 수 있으므로 종료시간이 빠를수록 다른 학생이 책을 읽을 수 있는 기회가 더 많이 주어집니다. 따라서, 종료 시간을 기준으로 정렬합니다.


Arrays.sort(reading, new Comparator<int[]>() {
			@Override
			public int compare(int[] start, int[] end) {
				if (start[1] == end[1]){
					return Integer.compare(start[0], end[0]);
				}
				return Integer.compare(start[1], end[1]);
			}
});

한 명이 책을 다 읽으면 곧바로 다른 사람한테 책을 넘길 수 있고, 다시 종료 시간을 갱신해야 합니다. 최대 학생 수를 구해야 하기 때문에 책을 넘길 때마다 학생 수를 카운트합니다.


int cnt = 0;    
int end = -1;   
for (int i = 0; i < N; i++) {
		if (reading[i][0] >= end) {
				end = reading[i][1];    
				cnt++;
		}
}

다른 책을 빌려서라도 모든 학생들이 책을 읽을 수 있도록 하기 위해서는 책을 읽기 시작하는 시간을 기준으로 정렬해야 합니다. 한 명이 3시에 책을 다 읽을 수 있는데 다른 학생이 2시부터 책 읽기가 가능하다면 책을 한 권 더 대출하면 됩니다.


Arrays.sort(reading, new Comparator<int[]>() {
		@Override
		public int compare(int[] start, int[] end) {
				if(start[0] == end[0]){
					return Integer.compare(start[1], end[1]);
				}
				return Integer.compare(start[0], end[0]);
		}
});

책을 읽기 시작하는 시점은 학생마다 다르고, 어떤 학생이 내가 책을 읽기 시작하는 시간보다 더 빨리 책을 읽게 되면 그 책을 이어서 읽을 수 있기 때문에 이를 위해서 우선순위 큐를 사용합니다.


for (int i = 0; i < N; i++) {
     if (!pq.isEmpty() && pq.peek() <= reading[i][0]){
         pq.poll();
     }
     pq.add(reading[i][1]);
}

우선순위 큐의 역할이 학생들에게 책을 배정하는 것이므로 우선순위 큐의 크기가 책의 최소 대출 권수가 됩니다.


answer[1] = pq.size();