백준 20207 달력(JAVA)

문제

 

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

20207번: 달력

코드

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static boolean[][] calendar = new boolean[1000][366];
    static int[] Height = new int[366];
    static PriorityQueue<int[]> input;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int S, E, Level, ans = 0;
        int[] q;
        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;
        });

        N = Integer.parseInt(br.readLine());

        //정렬
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            S = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            input.add(new int[]{S, E});
        }

        //일정 표시하기
        for (int i = 0; i < N; i++) {
            q = input.poll();
            S = q[0];
            E = q[1];

            Level = 0;

            for (int j = S; j <= E; j++) {
                if (calendar[Level][j] == true) {
                    Level++;
                    j = S - 1;
                }
            }

            for (int j = S; j <= E; j++) {
                calendar[Level][j] = true;
            }
        }

        //높이 계산하기
        for (int i = 1; i <= 365; i++) {
            int max = 0;
            for (int j = 0; j < 1000; j++) {
                if (calendar[j][i])
                    max = Math.max(j + 1, max);
            }
            Height[i] = max;
        }

        int w = 0, h = 0;
        //코팅하기
        for (int i = 1; i <= 365; i++) {
            if (Height[i] == 0) {
                ans += w * h;
                w = 0;
                h = 0;
            } else {
                w++;
                h = Math.max(Height[i], h);
            }
        }

        if (Height[365] != 0)
            ans += w * h;

        System.out.println(ans);
        br.close();

    }
}

풀이

풀이 자체는 쉽게 생각할 수 있는 문제였다. 하지만 문제의 조건인 시작하는 “날짜가 빠른순서대로”라는 말을 간과하여 오답이 났던 문제였다. 또한 1년의 마지막날까지 일정이 차있는 경우 역시 생각했어야 했다.

풀이는 다음과 같다.

우선 boolean 형식으로 가로는 365의 길이를 가진 배열을 세로로는 1000의 길이를 가진 배열을 만들고 전부 false로 초기화를 한다. 그리고 입력으로 들어오는 시작날짜와 마치는 날짜를 하나의 배열로 묶어 PriorityQueue에 넣어 정렬을 진행한다. 그 후 큐에서 차례대로 꺼내어 주면서 달력에 표시를 한다. 그리고 365일을 순회하면서 해당 날짜에 있는 일정들의 높이를 계산하고 코팅지의 길이를 계산해준다. (일정들의 높이가 0을 기준으로 하여 계산한다.)