[백준] 20207번 달력 JAVA (구현, Implementation)

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

 

풀이 1번 : 사각형 면적 구하기

 

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

// The main method must be in a class named "Main".
class Main {
    public static int[][] arr;
    public static int N;
    public static class Pair {
        int start, end;

        public Pair(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        PriorityQueue<Pair> pq = new PriorityQueue<>((e1,e2)->{
            if(e1.start == e2.start) {
                return e2.end - e1.end;
            }
            return e1.start - e2.start;
        });

        int max = 0;
        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 Pair(start,end));
            max = Math.max(end,max);
        }
        arr = new int[N][max+2];

        //달력 만들기
        while(!pq.isEmpty()) {
            Pair current = pq.poll();
            for (int i = 0; i<N;i++){
                if (arr[i][current.start] == 1){
                    continue;
                }
                for (int j= current.start ; j <=current.end;j++) {
                    arr[i][j] = 1;
                }
                break;
            }
        }
        //계산하기
        int widestart = 365;
        int wideend = 0;
        int height = 0;
        int areasum = 0;
        for (int j = 1; j< arr[0].length;j++){
            boolean stop = true;
            for (int i = 0; i < N;i++) {
                if (arr[i][j]==1){
                    wideend = Math.max(wideend,j);
                    widestart=Math.min(widestart,j);
                    height = Math.max(height, i+1);
                    stop = false;
                }
            }
            if (stop) {
                areasum += ((wideend - widestart + 1) * height);
                widestart = 365;
                wideend = 0;
                height=0;
            }
        }
        
        
        
        
        System.out.println(areasum);
    }
}

 

풀이 2번: 높이만으로 넓이 구하기

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

// The main method must be in a class named "Main".
class Main {
    public static int[] arr;
    public static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[367];
        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());
            for (int j = start ; j <= end; j++){
                arr[j]++;
            }
        }
        int row = 0;
        int col = 0;
        int result = 0;

        for (int i = 1; i <367;i++) {
            if (arr[i]>0){
                col++;
                row = Math.max(row,arr[i]);
            } else if (arr[i]==0) {
                result += (col * row);
                row = 0;
                col = 0;
            }
        }
        
        
        
        
        
        System.out.println(result);
    }
}

 

 

 

배운 점

      PriorityQueue<Pair> pq = new PriorityQueue<>((e1,e2)->{
            if(e1.start == e2.start) {
                return e2.end - e1.end;
            }
            return e1.start - e2.start;
        });