[BOJ/Java] 달력 (20207)

달력 (20207)

1. 문제 분석

문제 개요

• 캘린더에 여러 일정이 주어질 때, 일정이 겹치는 부분이 있는 날들의 면적을 구하는 문제다.
• 일정은 시작일과 종료일이 주어지며, 이 기간 동안 하루하루마다 그 일정을 처리한다.

입력 형식

• 첫 줄에 일정의 개수 N이 주어진다.
• 다음 N줄에는 각 일정의 시작일 x와 종료일 y가 주어진다.

출력 형식

• 전체 캘린더에서 일정이 겹치는 부분의 면적을 출력한다.

2. 알고리즘 종류

이 문제는 배열을 사용한 구간 처리 문제로, 일정의 범위에 맞춰 배열을 업데이트하고, 최종적으로 겹치는 부분의 면적을 계산하는 방식으로 해결할 수 있다.

3. 주요 부분 및 코드 작성 방법

1. 배열 사용

• page 배열을 사용하여 각 날짜마다 일정의 개수를 저장한다.
• 각 일정의 시작일부터 종료일까지 배열을 업데이트한다.

2. 면적 계산

• 배열을 순회하면서 연속된 일정의 면적을 계산한다.
• 연속된 일정이 끝날 때마다, 그 구간의 면적을 계산하여 결과에 더한다.

4. 코드 설명

메인 함수 (main)

import java.util.Arrays;
import java.util.Scanner;

public class Day0730_BOJ20207 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성

        int N = sc.nextInt(); // 일정의 개수 입력
        int[] page = new int[1000]; // 날짜별 일정 개수를 저장할 배열
        int max = 0; // 최대 종료일 저장 변수

        // 각 일정 처리
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt(); // 일정의 시작일
            int y = sc.nextInt(); // 일정의 종료일

            if (max < y) max = y; // 최대 종료일 업데이트

            // 일정 범위에 해당하는 날짜의 개수 증가
            for (int j = x; j <= y; j++) {
                page[j]++;
            }
        }

        // 마지막 날짜까지 카운팅하기 위해 배열 크기 조정
        page = Arrays.copyOf(page, max + 2);

        int height = 0; // 연속된 일정 중 가장 긴 일정
        int width = 0; // 연속된 일정의 길이
        int result = 0; // 전체 면적 결과

        // 배열을 순회하면서 면적 계산
        for (int i = 0; i < page.length; i++) {
            // 일정이 없는 날의 경우, 이전 구간의 면적을 결과에 더하고 초기화
            if (page[i] == 0) {
                result += height * width;
                height = 0;
                width = 0;
                continue;
            } else {
                // 연속된 일정 중 가장 긴 일정 높이 업데이트
                if (height < page[i]) height = page[i];
                width++; // 연속된 일정 길이 증가
            }
        }

        // 최종 결과 출력
        System.out.println(result);
    }
}

5. 전체 코드

import java.util.Arrays;
import java.util.Scanner;

public class Day0730_BOJ20207 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성

        int N = sc.nextInt(); // 일정의 개수 입력
        int[] page = new int[1000]; // 날짜별 일정 개수를 저장할 배열
        int max = 0; // 최대 종료일 저장 변수

        // 각 일정 처리
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt(); // 일정의 시작일
            int y = sc.nextInt(); // 일정의 종료일

            if (max < y) max = y; // 최대 종료일 업데이트

            // 일정 범위에 해당하는 날짜의 개수 증가
            for (int j = x; j <= y; j++) {
                page[j]++;
            }
        }

        // 마지막 날짜까지 카운팅하기 위해 배열 크기 조정
        page = Arrays.copyOf(page, max + 2);

        int height = 0; // 연속된 일정 중 가장 긴 일정
        int width = 0; // 연속된 일정의 길이
        int result = 0; // 전체 면적 결과

        // 배열을 순회하면서 면적 계산
        for (int i = 0; i < page.length; i++) {
            // 일정이 없는 날의 경우, 이전 구간의 면적을 결과에 더하고 초기화
            if (page[i] == 0) {
                result += height * width;
                height = 0;
                width = 0;
                continue;
            } else {
                // 연속된 일정 중 가장 긴 일정 높이 업데이트
                if (height < page[i]) height = page[i];
                width++; // 연속된 일정 길이 증가
            }
        }

        // 최종 결과 출력
        System.out.println(result);
    }
}