백준 20207번 : 달력 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

20207번 달력 골드 5

 

📖 문제

 

열 : 365 + 2 (1부터 365까지, 그리고 마지막에 값이 남은채로 계산되는 거 방지용)

행 : 중복 일정 가능성 1000개

높이 배열 하나 생성

 

입력 값은 시작 날짜가 빠른 순, 같다면 길이가 긴 순으로 오름차 정렬

→ 근데 시작 날짜가 빠른 순으로 해도 된다.

 

일정에 각 날짜 기간 저장, 중복이라면 현재 행 + 1에 날짜 기간 저장

0 행에는 중첩 날짜를 이어서 저장

높이 배열에는 각 날짜의 높이 최댓값을 저장

 

그리고 0행의 일정을 쭉 탐색해서 길이를 구하고 최대 높이를 구한다음 

길이 * 높이를 더해 코팅지 면적을 구한다.

 

---

🔅 문제 풀이

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

public class Main {
    // 이중 배열로 [1001][367]을 생성, 1~365일 동안 1000개의 중복 일정을 대비
    // 각 날짜의 0인덱스는 중복일정을 이어붙여서 체크 할 예정
    // 각 날짜의 최대 중복 수를 기록할 배열 생성
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] - o2[0] == 0) {
                return o2[1] - o1[1];
            }
            return o1[0] - o2[0];
        }); // 날짜들을 시작 날짜 순으로, 같다면 긴 일정 먼저

        boolean[][] calendar = new boolean[1001][367];
        int[] height = new int[366];

        int n = Integer.parseInt(br.readLine());

        // 우선순위 큐에 일정들을 넣는다.
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            pq.add(new int[] {start, end});
        }


        // 일정들을 날짜 배열에 넣어 처리
        while (!pq.isEmpty()) {
            int[] day = pq.poll();
            int start = day[0];
            int end = day[1];

            // 일정 채우기
            for (int i = 1; i < calendar.length; i++) {
                // 중첩 일정이 있으면 그 아래에 일정 표시
                if (!calendar[i][start]) {
                    for (int j = start; j <= end; j++) {
                        calendar[0][j] = true; // 0인덱스에 중첩 일정 단위를 기록
                        calendar[i][j] = true;
                        height[j] = i; // 높이 값 기록
                    }

                    break;
                }
            }
        }

        int sum = 0;
        int dayCnt = 0;
        int maxHeight = 1;


        // 0인덱스와 height을 사용하여 중복 일정 넓이와 높이를 구함
        for (int i = 1; i < calendar[0].length; i++) {
            if (calendar[0][i]) {
                maxHeight = Math.max(maxHeight, height[i]);
                dayCnt++;
            } else if (dayCnt != 0){
                sum += dayCnt * maxHeight;
                maxHeight = 1;
                dayCnt = 0;
            }
        }


        bw.write(sum + "");  // 출력 내용 작성
        bw.flush();
        bw.close();
    }
}

 

🔅 다른 사람 풀이 이해해보기

날짜 일차원 배열을 생성하고

시작일에 +1, 끝나는 일 + 1 에 - 1을 해준다. 

끝나는 일 + 1을 해주는 이유

• calendar[i] += calendar[i - 1] 로 이전 값 을 현재 값에 더해 0이 아니면 일정이 있다는 의미 
• 2,4 의 경우를 생각해보자. 2,4는 2,3,4 로 총 3일간의 일정이다.
• 하지만 끝나는 일에 -1을 하면 2에서 시작해서 4에 0이 되기에 2,3 총 2일간의 일정으로 되어버리기 때문

calendar[i] 의 값은 높이 즉, 중첩 일정 개수로 볼 수 있다.

 

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[] calendar = new int[367];

        int n = Integer.parseInt(br.readLine());

        // 우선순위 큐에 일정들을 넣는다.
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            calendar[start]++; // 시작점은 + 1
            calendar[end + 1]--; // 끝점은 - 1로 시작점에서 +1된 것을 회수 
        }

        int sum = 0;
        int dayCnt = 0;
        int maxHeight = 0;
        // 0인덱스와 height을 사용하여 중복 일정 넓이와 높이를 구함
        for (int i = 1; i < calendar.length; i++) {
            calendar[i] += calendar[i - 1]; // 이전 값을 더해서 0이 아니면 일정이 끝난 것이 아님
            if (calendar[i] == 0) {
                sum += dayCnt * maxHeight;
                dayCnt = 0;
                maxHeight = 0;

            } else {
                dayCnt++;
                maxHeight = Math.max(maxHeight, calendar[i]);
            }
        }


        bw.write(sum + "");  // 출력 내용 작성
        bw.flush();
        bw.close();
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  문제 그대로 적용하려다 보니 길게 코드를 짜게되었다. 다른 사람 코드는 매우 인상적이다. 까먹지 말고 익히자.