백준 20207 - 달력(Java)

www.acmicpc.net/problem/20207

20207번: 달력

1. 유형

시뮬레이션, 우선순위큐

 

2. 자료구조

우선순위큐

 

3, 구현 기능

- 달력 배열 만들기

- 우선순위큐에 정렬된 순서대로 달력에 표시

- 코딩지 설정

 

4. 풀이

사격형 구해서 풀이

 

코드.

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

public class Main {
	static int map[][], N;

	static class Pair {
		int start, end;

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

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		PriorityQueue<Pair> pq = new PriorityQueue<>((e1, e2) -> {
			if (e1.start == e2.start)
				return e2.end - e1.end;
			return e1.start - e2.start;
		});
		int maxday = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			int u = stoi(st.nextToken());
			int v = stoi(st.nextToken());
			pq.add(new Pair(u, v));
			maxday = Math.max(maxday, v);
		}
		map = new int[N][maxday + 2];
		// 달력 만들기
		while (!pq.isEmpty()) {
			Pair current = pq.poll();
			for (int i = 0; i < N; i++) {
				if (map[i][current.start] == 1)
					continue;
				for (int j = current.start; j <= current.end; j++) {
					map[i][j] = 1;
				}
				break;
			}
		}
		int widestart = 365;
		int wideend = 0;
		int height = 0;
		int areasum = 0;
		for (int j = 1; j < map[0].length; j++) {
			boolean stop = true;
			for (int i = 0; i < N; i++) {
				if (map[i][j] == 1) {
					wideend = Math.max(wideend, j);
					widestart = Math.min(widestart, j);
					height = Math.max(height, i + 1);
					stop = false;
				}
			}
			if (stop) {
				areasum += ((wideend - widestart + 1) * height);
				widestart = 365;
				wideend = 0;
				height = 0;
			}
		}
		System.out.println(areasum);
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}

---

배열에 높이값만 저장해서 풀이

 

세로와 가로를 알 수 있으므로 계산할 수 있다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = stoi(st.nextToken());
		int arr[] = new int[367];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine());
			int from=stoi(st.nextToken());
			int to=stoi(st.nextToken());
			for(int day=from; day<=to; day++) {
				arr[day]++;
			}
		}
		int row=0;
		int col=0;
		int result=0;
		for(int i=1;i<367;i++) {
			if(arr[i]>0) {
				col++;
				row=Math.max(row, arr[i]);
			}else if(arr[i]==0) {
				result += (col*row);
				col=0;
				row=0;
			}
			
		}
		System.out.println(result);
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}