[백준] 20207: 달력 - JAVA

in Algorithm on 구현

https://www.acmicpc.net/problem/20207

풀이

일정들의 시작, 종료 날짜가 주어지고, 달력에 배치해야 한다.

달력에 배치할 때 주의해야 할 규칙은 다음과 같다.

  • 시작일이 가장 앞선 일정부터 차례대로 채워진다.

  • 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.

  • 일정은 가능한 최상단에 배치된다.

365일만큼 배열을 만들고, 일정이 있는 구간에 +1하여 누적합했다.

빈칸이 있으면 최상단에 배치되기때문에 누적합하여 높이와 길이를 정할 수 있기 때문이다.

일정이 없는 날짜가 나오면 이전까지 누적했던 길이 * 높이를 답에 더해주었다.

메모리: 14480KB

시간: 136ms

언어: Java 11

코드

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));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        int[] calendar = new int[365 + 2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            calendar[start]++;
            calendar[end + 1]--;
        }

        int answer = 0;
        int length = 0;
        int height = 0;
        for (int i = 1; i < calendar.length; i++) {
            calendar[i] += calendar[i - 1];
            if (calendar[i] == 0) {
                answer += length * height;
                length = 0;
                height = 0;
            } else {
                length++;
                height = Math.max(calendar[i], height);
            }
        }

        System.out.println(answer);
    }

}