[백준] 달력 : 20207 - JAVA

[Gold V] 달력 - 20207

20207번: 달력

성능 요약

메모리: 16420 KB, 시간: 164 ms

분류

그리디 알고리즘, 구현, 정렬

문제 설명

수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다.

여름이 거의 끝나가자 장마가 시작되었고, 습기로 인해 달력에 표시한 일정이 지워지려고 한다. 지워지는 것을 막고자 수현이는 일정이 있는 곳에만 코팅지를 달력에 붙이려고 한다. 하지만 너무 귀찮았던 나머지, 다음과 같은 규칙을 따르기로 한다.

• 연속된 두 일자에 각각 일정이 1개 이상 있다면 이를 일정이 연속되었다고 표현한다.
• 연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.
• 연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.

달력은 다음과 같은 규칙을 따른다.

• 일정은 시작날짜와 종료날짜를 포함한다.
• 시작일이 가장 앞선 일정부터 차례대로 채워진다.
• 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
• 일정은 가능한 최 상단에 배치된다.
• 일정 하나의 세로의 길이는 1이다.
• 하루의 폭은 1이다.

위의 그림에서와 같이 일정이 주어졌다고 하자. 여기서 코팅지의 면적은 아래의 파란색 영역과 같다.

이때 코팅지의 크기의 합은 3 x 8 + 2 x 2 = 28이다.

일정의 개수와 각 일정의 시작날짜, 종료날짜가 주어질 때 수현이가 자르는 코팅지의 면적을 구해보자.

입력

첫째 줄에 일정의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

둘째 줄부터 일정의 개수만큼 시작 날짜 S와 종료 날짜 E가 주어진다. (1 ≤ S ≤ E ≤ 365)

출력

코팅지의 면적을 출력한다.

---

🧐 어떻게 풀까?

문제를 해결하기 위해 구해야할 것을 정한다. 연속된 일정을 가릴 수 있는 코팅지의 면적을 구해야하므로 즉 가로 세로를 구해야한다.

가로는 연속 일정(시작일, 마지막일) 정보이고 세로는 쌓여있는 크기이다.

 

연속일정을 구하기 위해서는 겹쳐져 있는 일정들을 적절하게 하나로 만들어줘야 한다. 시작일과 마지막일을 모두 입력 받고 시작일을 기준으로 오름차순으로 우선순위 큐에 넣어야한다. 큐에서 요소를 하나씩 빼면서 현재 일정의 시작일이 전의 일정의 마지막날과 연속되거나 겹치는지 확인한다. 겹친다면 같은 연속된 일정인 것이고, 겹치는 것이 아니면 새로운 일정의 시작으로 취급한다. 같은 연속된 일정일 때는 일정의 마지막날을 비교하여 더 큰 쪽으로 갱신한다.

 

세로 크기를 구하기 위해서는 연속된 일정 중 가장 많이 겹치는 날을 알아내야 한다. 365개의 int []을 생성하여,  입력값으로 일정을 입력받을 때 시작일 부터 마지막일까지 범위내에 있는 요소에 +1을 해준다. 

 

풀이 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

/*
	구해야 하는 것 : 연속된 정보, 너비
	너비 : 쌓아야 한다. -> 365 배열을 만들고 포함되면 count 한다
	연속 정보 :입력 정보를 받고 시작일 기준으로 정렬 후 연속 날 합치
 */
public class Main {

	public static BufferedWriter bw;
	public static BufferedReader br;

	public static int [] counts;
	public static PriorityQueue<Schedule> schedules;


	public static void main(String[] args) throws Exception {

		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		counts = new int[366];
		schedules = new PriorityQueue<Schedule>();

		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 day=start; day<=end; day++) {
				counts[day]++;
			}

			schedules.add(new Schedule(start, end));
		}

		// 연속된 일정 합치기
		int sum = 0;

		Schedule cur = schedules.poll();
		int preStart = cur.start;
		int preEnd = cur.end;

		while(!schedules.isEmpty()) {
			cur = schedules.poll();

			// 새로운 일정 시작
			if(cur.start > preEnd+1) {

				// 전의 일정 직사각형 구하기
				int max = -1;
				for(int i=preStart; i<=preEnd; i++) {
					max = Math.max(counts[i], max);
				}
				sum += (preEnd - preStart +1)*max;

				// 새로운 일정으로 업데이트
				preStart = cur.start;
				preEnd = cur.end;
			}
			// 연속적인 일정일 때
			else {
				preEnd = Math.max(cur.end, preEnd);
			}
		}
		// 마지막 일정 직사각형 구하기
		int max = -1;
		for(int i=preStart; i<=preEnd; i++) {
			max = Math.max(counts[i], max);
		}
		sum += (preEnd - preStart +1)*max;

		System.out.println(sum);
	}
}
class Schedule implements Comparable<Schedule>{
	int start;
	int end;

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

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


}