[백준/JAVA] 20207번: 달력

🔺 문제

20207번: 달력

 

 

🧩  해결 아이디어

• 구현

1. 구간을 입력받고, 해당 시작점부터 끝점까지 구간을 색칠한다.
   → 카운트 배열 사용
2. 카운트 배열을 돌면서 해당 칸의 값이 0이 아니라면 너비 + 1하고 높이는 최대 높이와 비교해 더 큰 값으로 갱신한다.
   / 해당 칸의 값이 0이라면, 여태까지 구한 너비와 최대 높이를 구해 넓이 값에 누적해 저장하고, 너비와 최대 높이는 0으로 초기화한다.
3. ⭐ 마지막 구간 처리를 위해 마지막에 넓이들의 합에 너비 * 최대 높이 구한 값을 더해줘야 한다!!

 

 

💥 유의사항

마지막 구간 처리를 놓치면 안 된다. 😱

그럼 1%에서 틀리는 불상사 발생,,

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int DAY_OF_YEAR = 365;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int[] cntArr = new int[DAY_OF_YEAR + 1];    // 카운팅 배열
        
        while(N --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            
            // 구간 색칠하기
            for(int i = from ; i <= to ; i++) { 
                cntArr[i]++;
            }
        }
        
        int total = 0;
        int w = 0;
        int maxH = 0;
        
        for(int i = 0 ; i <= DAY_OF_YEAR ; i++) {
            if(cntArr[i] != 0) {
                w++;
                maxH = Math.max(maxH, cntArr[i]);
            }
            else {
                total += w * maxH;
                
                // 너비와 최대 높이 초기화
                w = 0;
                maxH = 0;
            }
        }
        
        total += w * maxH;  // 마지막꺼 처리 !!
        System.out.println(total);
    }
}
 

 

 

---

🔺 다른 풀이들

우선순위 큐 사용하셔서 정렬하시고 하는 풀이도 있었는데,

이 문제에서 정렬은 필요하지 않다고 생각돼서 링크를 달진 않겠다..

 

---

💬 느낀 점

단순 구현이라 어려운 문제는 아닌데 카운팅 정렬 쓸 생각을 45분만에 했고,

코드 작성하고 에러 잡는데 40분? 걸린 것 같다.

 

게시판에 올라온 반례도 심지어 다 맞길래 뭐지-하고 다른 분들 코드를 참고했다ㅠ

 

문제 조건에 정렬이 있길래 정렬해야 하나? 했는데 정렬할 필요 없고,

그냥 지나간 횟수 누적해주면 되는 것이었다.

 

그리고 마지막 구간 처리까지 놓치면 안 되는!!

 

담에는 더 빨리 생각해서 잘 풀어보겠다,,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[자바] 백준 20207 - 달력 (java)

 

백준 20207 - 달력(Java)