백준 20207 - 달력

Java

20207 번 - 달력

문제

접근 방법

문제의 조건 중

• 시작일이 가장 앞선 일정부터 차례대로 채워진다.
• 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.

를 구현하기 위해 Priority Queue를 사용하였다.

정렬된 일정을 달력에 하나씩 채운 뒤,
1일 부터 0~999 까지 총 1000개의 세로를 탐색한다.

하나라도 일정이 있으면, 그 일정의 시작일을 코팅지의 시작으로 한다.
이후 해당 일에 1000개의 세로 중 하나라도 일정이 없으면 코팅지의 끝으로 보고 현재까지의 높이와 일정 차이를 구하여 결과 값에 계속 더하면서 답을 구한다.

코드

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

public class Main {
	static int n, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	int s,e;
    	int[][] calen = new int[1001][367];
		// 일정 정렬
    	PriorityQueue<int[]> input = new PriorityQueue<>((o1,o2)->{
    		int comp = Integer.compare(o1[0], o2[0]);
			if(comp == 0) {
				return -Integer.compare(o1[1], o2[1]);
			}
			else
				return comp;
    	});

    	while(n-- != 0) {
    		stk = new StringTokenizer(br.readLine());
    		s = stoi(stk.nextToken());
    		e = stoi(stk.nextToken());
    		input.add(new int[] {s,e});
    	}

		// 달력에 일정 삽입
    	int[] q;
    	while(!input.isEmpty()) {
    		q = input.poll();
    		s = q[0];
    		e = q[1];

    		next: for(int i = 0; i < 1000; i++) {
    			for(int j = s; j <= e; j++) {
    				if(calen[i][j] != 0)	// 하나라도 일정이 있으면 다음 높이로 이동
    					continue next;
    			}
    			for(int j = s; j <= e; j++) {
    				calen[i][j] = 1;
    			}
    			break;
    		}
    	}
    	s = -1;
    	int h = 0;
    	boolean isEnd = false;
		// 1일부터 366일 까지 탐색
		// 366일 까지 탐색하는 이유는, 365일이 마지막이므로 365일에 채워져 있으면 366일에 비어있어야 넓이 계산이 되기 때문
    	for(int i = 1; i <= 366; i++) {
    		isEnd = true;
    		for(int j = 0; j < 1000; j++) {
    			if(calen[j][i] != 0) {
    				if(s == -1)		// 코팅지의 시작이라면
    					s = i;
    				isEnd = false;
    				h = Math.max(h, j + 1);
    			}
    		}
			// 코팅지 넓이 계산
    		if(isEnd) {
    			result += h * (i - s);
    			s = -1;
    			h = 0;
    		}

    	}
    	System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

문제의 조건 중, 무시해도 되겠지 하고 안일하게 생각하였다 틀렸던 문제.
문제의 조건이 있는 이유는 있었다..

개선할 점