[BaekJoon] 2672 여러 직사각형의 전체 면적 구하기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int rectangleCount;
    static int max;
    static int[] rectangleCounts;
    static List<Vertical> verticals;

    static void input() {
        Reader scanner = new Reader();

        rectangleCount = scanner.nextInt();
        max = 0;
        verticals = new ArrayList<>();

        for (int count = 0; count < rectangleCount; count++) {
            double startX = scanner.nextDouble();
            double startY = scanner.nextDouble();
            double width = scanner.nextDouble();
            double height = scanner.nextDouble();

            // 직사각형의 시작 지점을 추가
            verticals.add(
                    new Vertical((int) (startX * 10), (int) (startY * 10), (int) (startY * 10) + (int) (height * 10),
                            1));
            // 직사각형의 끝 지점을 추가
            verticals.add(new Vertical((int) (startX * 10) + (int) (width * 10), (int) (startY * 10),
                    (int) (startY * 10) + (int) (height * 10), -1));
            // 최대 y 좌표 갱신
            max = Math.max(max, (int) (startY * 10) + (int) (height * 10));
        }
    }

    /*
     * 모든 입력은 소수점 이하 한 자리까지 주어지기 때문에 이에 10을 곱하여 정수로 표현하고 정수를 이용해 답을 구한다
     * 구한 면적을 100으로 나눠주면 소수점 이하 2자리까지 출력할 수 있다
     *
     * 주어진 직사각형을 x좌표를 기준으로 시작 지점과 끝 지점으로 나눈다
     * 각 직사각형에 대해 x좌표를 기준으로 시작 지점에서 끝 지점까지 이동하며 시작 지점부터 끝 지점까지 y좌표들이 차지하고 있는 부분을 구한다
     * 해당 부분의 면적을 누적해 더해나가며 전체 면적을 구한다
     */
    static void solution() {
        rectangleCounts = new int[max + 1]; // 각 y좌표에서 직사각형의 개수를 의미하는 배열
        Collections.sort(verticals);
        long answer = calculateArea();
        print(answer);
    }

    static void print(long answer) {
        if (answer % 100 == 0) { // 총 면적이 정수로 맞아떨어진다면
            // 정수 부분만 출력한다
            System.out.println(answer / 100);
        } else { // 그렇지 않다면
            // 소수점 이하 2자리까지 출력한다
            double a = 0;
            a = (double) answer / 100;
            System.out.println(String.format("%.2f", a));
        }
    }

    static long calculateArea() {
        long answer = 0L; // 총 면적
        int x = 0; // 이전 x좌표

        for (Vertical vertical : verticals) {
            // 현재까지 직사각형이 차지하고 있는 곳의 개수를 계산
            int count = findRectangleCount();
            // 이전 x좌표부터 현재 x좌표까지 면적을 계산
            answer += count * (vertical.x - x);
            // 직사각형이 차지하고 있는 곳을 갱신
            updateRectangleCounts(vertical);
            // 이전 x 좌표 갱신
            x = vertical.x;
        }

        return answer;
    }

    static int findRectangleCount() {
        int count = 0;
        // 직사각형이 시작하는 곳을 1, 끝나는 곳을 -1로 해놨기 때문에
        // 0보다 큰 곳은 현재 직사각형이 차지하고 있는 곳이다
        // 그러므로 0보다 큰 곳의 개수를 구한다
        for (int idx = 0; idx <= max; idx++) {
            if (rectangleCounts[idx] > 0) {
                count++;
            }
        }
        return count;
    }

    static void updateRectangleCounts(Vertical vertical) {
        for (int idx = vertical.startY + 1; idx <= vertical.endY; idx++) {
            if (vertical.isStart == 1) { // 현재 vertical이 시작 지점이라면
                // 직사각형이 차지하고 있는 y좌표들에 대해 1 더한다
                rectangleCounts[idx]++;
            } else { // 끝나는 지점이라면
                // 직사각형이 차지하고 있는 y좌표들에 대해 -1을 더하여 더이상 차지하지 않음을 나타낸다
                rectangleCounts[idx]--;
            }
        }
    }

    static class Vertical implements Comparable<Vertical> {
        int x;
        int startY;
        int endY;
        int isStart;

        public Vertical(int x, int startY, int endY, int isStart) {
            this.x = x;
            this.startY = startY;
            this.endY = endY;
            this.isStart = isStart;
        }

        @Override
        public int compareTo(Vertical o) {
            if (x != o.x) {
                return x - o.x;
            }
            return isStart - o.isStart;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}