백준 - 2669번(직사각형 네개의 합집합의 면적 구하기)

문제 출처: https://www.acmicpc.net/problem/2669

문제

• 평면에 네 개의 직사각형이 놓여 있는데 그 밑변은 모두 가로축에 평행하다. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고, 겹쳐 있을 수도 있고, 하나가 다른 하나를 포함할 수도 있으며, 변이나 꼭짓점이 겹칠 수도 있다.

• 이 직사각형들이 차지하는 면적을 구하는 프로그램을 작성하시오.
  

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = new int[16];
        int maxX = 0;
        int maxY = 0;
        int count = 0;

        int index = 0;

        for (int i = 0; i < 4; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int j = 0; j < 4; j++) {
                arr[index + j] = Integer.parseInt(tokenizer.nextToken());
            }
            maxX = Math.max(arr[index + 3], maxX); // 행
            maxY = Math.max(arr[index + 2], maxY); // 열
            index += 4;
        }

        int[][] matrix = new int[maxX][maxY];

        for (int i = 0; i < 16; i += 4) {
            int startX = arr[i + 1];
            int startY = arr[i];
            int endX = arr[i + 3];
            int endY = arr[i + 2];

            for (int j = startX; j < endX; j++) {
                for (int k = startY; k < endY; k++) {
                    matrix[j][k] = 1;
                }
            }
        }

        for (int i = 0; i < maxX; i++) {
            for (int j = 0; j < maxY; j++) {
                if (matrix[i][j] == 1) count++;
            }
        }

        System.out.println(count);
    }

}

• 어떻게든 쉽게 풀어보려 고민하느라 난이도에 비해 많은 시간이 소요됐다.
• 들어오는 점들에서 최대 행과 최대 열의 숫자를 구한다. 오른쪽 점인 뒤에 2개 값으로 구하는데, 입력값은 xy 좌표계에 따라 들어오므로 배열에 대응하기 편하게 x는 행 변수, y는 열 변수로 두어 끝에서 2번째는 y, 마지막은 x에 저장하였다.
• 모든 사각형을 수용할 수 있는 크기의 배열을 구성하고, 각 사각형들이 차지하는 공간을 1로 바꾼 뒤 1의 갯수를 셌다.
• 문제를 다 풀고 다른 사람들의 코드를 보니 전부 배열 크기를 100으로 두었다. 왜 그랬을까 의아해하며 문제를 다시 읽어보니 수의 범위가 100이하 자연수로 있었다;; 문제를 잘 읽어야겠다 정말 ㅜㅜ😥