Baekjoon_20207_달력

문제 설명

20207번: 달력

 

• 일정의 개수 N
• 시작날짜 S와 종료날짜 E가 N개 주어짐
• 일정채우기 : 시작날짜가 앞선 것부터, 같은 시작날짜라면 일정이 긴 것부터(종료날짜가 나중인 것부터)
• 전부 일정을 채운 후, 코팅지를 직사각형으로 잘라 일정을 감싼다.

=> 모든 일정을 감싸기 위해 자르는 코팅지의 최소 면적 출력

 

 

문제 풀이

우선 calender라는 클래스를 하나 만들어 시작시간과 종료시간을 저장할 수 있도록 했다.

 

그리고 Comparable 인터페이스를 이용해 비교하기 위한 compareTo를 만들어주었다.

시작시간을 오름차순으로 정렬하면서 만약 시작시간이 같을 경우 끝시간이 큰 것이 먼저 나오게 했다.

 

각 행의 최대 열값을 저장하는 배열과 각 열의 최대 행값을 저장하는 배열을 만들어 다음 그림과 같은 값이 들어가도록 구현했다.

 

이후 maxColumnNum이 0이 아닐때(1일)~ 0이 아닐때(10일) 안의 최대 행 값을 구하여 사각형의 너비를 구했고, 전부 더해 출력했다.

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _20207_달력 {
	static class calender implements Comparable<calender>{
		int S;
		int E;
		calender(int S, int E){
			this.S = S;
			this.E = E;
		}
		@Override
		public int compareTo(calender o) {
			// TODO Auto-generated method stub
			if(o.S == this.S) {
				return o.E - this.E;	//시작일이 같다면 끝나는 날이 큰 것부터
			}
			return this.S - o.S;		//시작이 작은 것부터
		}
		
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		PriorityQueue<calender> pQueue = new PriorityQueue<>();
		StringTokenizer st;
		int maxColumnNum[] = new int[1001];		//각 행의 최대 열값 저장
		int maxRowNum[] = new int[367];			//각 열의 최대 행값 저장
		for(int i = 0; i<N;++i) {
			st = new StringTokenizer(in.readLine());
			int S = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			pQueue.add(new calender(S,E));
		}
		int maxC = 0;
		while(!pQueue.isEmpty()) {
			calender cal = pQueue.poll();
			maxC = cal.E;
			for(int r = 1; r<=1000;++r) {	//일정을 위에서부터 채우면서
				if(maxColumnNum[r] < cal.S) {	//해당 행에 채워진 일정(최대 열값)보다 해당 일정의 시작 일자가 나중이라면
					for(int i = cal.S;i<=cal.E;++i) {
						maxRowNum[i] = Math.max(maxRowNum[i], r);	//각 열의 최대 행 값 정정
					}
					maxColumnNum[r] = cal.E;	//해당 행의 최대 열값을 추가한 일정의 종료일자로 변경
					break;
				}
			}
		}
		
		int answer = 0;
		for(int c = 1;c<=maxC;++c) {
			if(maxRowNum[c] != 0) {	//0이 아닌 부분(일정이 있는 부분)
				int R = maxRowNum[c];
				int startC = c;	//시작 열값
				while(maxRowNum[c] != 0) {
					R = Math.max(R, maxRowNum[c++]);	//해당 열 범위 안 최대 행 값 구하기
				}
				answer += R *(c - startC);	//사각형 범위 값 더하기
			}
		}
		System.out.println(answer);
		
	}
}