[JAVA] 백준 20207 - 달력

 

🤔 문제 접근

구현 알고리즘의 달력 문제다.

연속된 각 일정들의 (최대 연속 일수) * (일정이 가장 많이 겹친 횟수) 로

각 일정들이 만들어내는 직사각형의 넓이를 구하면 되는 문제다.

 

우선 순위 큐를 이용하고 정렬 기준을 재정의하여 시작 일정이 빠른 순으로

각 일정들의 시작과 종료 일을 배열에 담아 큐에 저장했다.

그리고 이전 시작(preStart) 이전 종료(preEnd)를 기억해두고

큐에서 일정들을 하나씩 빼오도록 했다.

 

빼온 일정이 이전 일정과 연속된 일정인 경우 해당 일정의 최대 가로 길이를 

구하기 위해 preEnd와 curEnd의 대소 비교를 통해 최대값으로 갱신하도록 했다.

 

하나의 연속된 일정의 넓이는 연속되지 않은 일정이 등장할 때 구하도록 했다.

가로 길이는 curEnd - preStart + 1이고

세로 길이는 preStart 부터 preEnd까지 순회하여 가장 많이 겹친 일정의 value이다.

 

그리고 연속되지 않은 현재 일정들의 시작과 종료 날짜를

이전 일정의 시작과 종료 날짜로 갱신하였다.

 

이때 while 루프의 종료 조건이 우선 순위 큐가 비어있는 경우이기 때문에

마지막 일정의 넓이를 구하지 않고 totalSize를 출력할 수도 있으므로

마지막 일정의 넓이를 한번 더 구한 뒤 결과를 출력한다.

 

 

🚨CODE

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

/*
 * 구해야하는 것 : 각 일정이 이루는 사각형들의 넓이 합
 * 가로 : 연속되는 일정의 최대-최소+1
 * 세로 : 겹치는 일정이 있다면 해당 날의 value + 1, 이후 최대 value가 세로가 된다.
 * 유의 사항 : 이어지지 않는 일정에 대해 신경써야 한다. 이것은 직전 일정의 종료일+1과 대소비교로 알 수 있다.
*/
public class Main {
	static int[] plan = new int[366];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 시작 일정이 빠른 순으로 정렬하는 우선 순위 큐 선언
		NewComparator newCom = new NewComparator();
		PriorityQueue<int[]> pq = new PriorityQueue<>(newCom);
		
		int n = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			for(int j = start; j<=end; j++) {
				plan[j]++;
			}
			
			pq.offer(new int[] {start,end});
		}
		
		int totalSize = 0;
		int[] cur = pq.poll();
		int preStart = cur[0];
		int preEnd = cur[1];
		
		while(!pq.isEmpty()) {
			
			cur = pq.poll();
			int curStart = cur[0];
			int curEnd = cur[1];

			// 직전 일정과 연속되지 않는 일정인 경우
			if(preEnd + 1 < curStart) {
				
				// 현재까지 일정의 넓이 구함
				int weight = preEnd - preStart + 1;
				int height = -1;
				
				for(int i = preStart; i<=preEnd; i++) {
					height = Math.max(height, plan[i]);
				}
				
				totalSize += weight * height;
				preStart = curStart;
				preEnd = curEnd;
			
			} 
			// 연속되는 일정일 때
			else {
				preEnd = Math.max(curEnd, preEnd);
			}
			
			
		} // end of while
		
		// 마지막 일정 넓이
		int height = -1;
		for(int i = preStart; i<=preEnd; i++) {
			height = Math.max(height, plan[i]);
		}
		totalSize += height * (preEnd - preStart + 1);
		
		System.out.println(totalSize);
	}
	
}

// 우선 순위 큐 정렬 기준 재정의
class NewComparator implements Comparator<int[]>{

	@Override
	public int compare(int[] o1, int[] o2) {
		// TODO Auto-generated method stub
		if(o1[0] < o2[0])
			return -1;
		else if(o1[0] > o2[0])
			return 1;
		else
			return 0;
	}
	
}