백준_Java_20207_달력

문제

백준 20207 - 달력

여러 일정이 주어질 때, 이를 달력에 배치하고 차지하는 직사각형 면적을 구하는 문제입니다. 일정은 시작일과 종료일로 주어지며, 겹치는 일정이 있는 경우 이를 높이로 표현합니다. 이를 통해 달력의 전체 면적(폭 × 높이)을 계산하는 것이 목표입니다.

---

풀이

1) 일정 마킹

• 날짜를 기준으로 일정의 시작과 끝을 배열에 기록합니다.
• 시작일에는 +1, 종료일 다음 날에는 -1을 기록하여 일정의 변화를 마킹합니다.
• 이를 통해 특정 날짜에 일정이 시작되고 끝나는 구간을 표시할 수 있습니다.

for (int[] pair : eventList) {
    int start = pair[0];
    int end = pair[1];
    board[start]++;
    board[end + 1]--;
}

 

예를 들어서 2~4, 1~3 구간은 아래처럼 마킹할수 있습니다.

날짜	1	2	3	4	5	6	...
2~4	0	1	0	0	-1	0
1~3	1	0	0	-1	0	0
합산	1	1	0	-1	-1	0

2) 누적합 계산

• 배열에 마킹된 값을 기반으로 누적합을 계산하여, 날짜별로 겹치는 일정의 개수를 구합니다.
• 누적합을 통해 특정 날짜의 높이(겹치는 일정 수)를 알 수 있습니다.

for (int i = 1; i < board.length; i++) {
    board[i] += board[i - 1];
}

 

예를 들어서 2~4, 1~3 구간은 아래처럼 누적합이 계산됩니다.

날짜	1	2	3	4	5	6	...
2~4	0	1	1	1	0	0
1~3	1	1	1	0	0	0
합산	1	2	2	1	0	0

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] eventList = new int[N][2];
        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(br.readLine());
            eventList[i][0] = Integer.parseInt(tokenizer.nextToken());
            eventList[i][1] = Integer.parseInt(tokenizer.nextToken());
        }

        int result = process(eventList);
        bw.write(result + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

    static int process(int[][] eventList) {
        // mark board
        int[] board = new int[367]; // 날짜 범위 1~365 + 추가 공간
        for (int[] pair : eventList) {
            int start = pair[0];
            int end = pair[1];
            board[start]++;
            board[end + 1]--;
        }

        // spread board
        for (int i = 1; i < board.length; i++) {
            board[i] += board[i - 1];
        }

        // calculate board area
        int area = 0;
        int max = 0;
        int start = -1;

        for (int i = 1; i < board.length; i++) {
            if (board[i] > 0) { // in rectanguler
                max = Math.max(max, board[i]);
                if (start == -1) { // start rectanguler
                    start = i;
                }
            } else if (start != -1) { // end rectanguler
                area += max * (i - start);
                max = 0;
                start = -1;
            } 
            // not in rectanguler
        }

        return area;
    }
}