[코드트리/자바] mid.simulation1.잔해물을 덮기 위한 사각형의 최소 넓이

문제

두 사각형의 좌표가 주어질 때, 두 사각형이 겹치는 부분을 제외한 첫 번째 사각형의 영역을 덮는 사각형의 최소 넓이를 구하여라.

 

해석

단순한 완탐 느낌으로 접근해서, 2차원 배열에 사각형을 그리고, 첫 번째 사각형의 남는 영역을 찾아서 그 영역의 긴 변의 곱을 출력하면 되겠다 생각했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        int[][] arr = new int[2001][2001];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        /*
        시간복잡도 : 최대 2000까지이므로 n^2 가능
        첫번째 사각형 : 각 좌표를 입력받아서 2차원 배열에 +1로 입력
        두번째 사각형 : 각 좌표를 입력받아서 2차원 배열에 +2로 입력
        브루트포스로 돌려서 1인 사각형의 x 최대 길이, y 최대 길이 확인
        각 최대 길이의 곱 출력;
        **/
        int x1,y1,x2,y2;
        for (int i = 0; i < 2; i++) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken()) + 1000;
            y1 = Integer.parseInt(st.nextToken()) + 1000;
            x2 = Integer.parseInt(st.nextToken()) + 1000;
            y2 = Integer.parseInt(st.nextToken()) + 1000;
            for (int j = x1; j < x2; j++) {
                for (int k = y1; k < y2; k++) {
                    if (i == 0) {
                        arr[j][k] += 1;
                    } else {
                        arr[j][k] += 2;
                    }
                }
            }
        }

        int[] len = new int[2001];
        for (int i = 0; i < 2001; i++) {
            int cnt = 0;
            for (int j = 0; j < 2001; j++) {
                if (arr[i][j] == 1) {
                    cnt++;
                }
            }
            len[i] += cnt;
        }
        long height = Arrays.stream(len).filter(i -> i > 0).count();
        int width = Arrays.stream(len).filter(i -> i > 0).max().orElseThrow(() -> new NoSuchElementException("no"));
        System.out.println(width * height);
    }
}

하지만 위 방식을 사용하면, 두 번째 사각형이 첫 번째 사각형을 가로지를때 발생하는 모양에 대응할 수 없다. 따라서 결국은 겹치지 않는 첫 번째 사각형의 영역 중 각 꼭짓점의 좌표를 알아야 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

public class Main {
    public static final int OFFSET = 1000;
    public static final int MAX_SIZE = 2000;
    public static void main(String[] args) throws IOException {
        int[][] arr = new int[MAX_SIZE + 1][MAX_SIZE + 1];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        /*
        시간복잡도 : 최대 2000까지이므로 n^2 가능
        첫번째 사각형 : 각 좌표를 입력받아서 2차원 배열에 +1로 입력
        두번째 사각형 : 각 좌표를 입력받아서 2차원 배열에 +2로 입력
        브루트포스로 돌려서 1인 사각형의 x 최대 길이, y 최대 길이 확인
        -> 최대 길이로 하게 되면 r1을 가로지르는 r2에 대하여 대응하지 못함
        -> 따라서, 결국은 1로 남은 사각형의 x1y1, x2,y2를 구해야 함

        **/
        int x1,y1,x2,y2;
        for (int i = 0; i < 2; i++) {
            st = new StringTokenizer(br.readLine());
            x1 = Integer.parseInt(st.nextToken()) + OFFSET;
            y1 = Integer.parseInt(st.nextToken()) + OFFSET;
            x2 = Integer.parseInt(st.nextToken()) + OFFSET;
            y2 = Integer.parseInt(st.nextToken()) + OFFSET;
            for (int j = x1; j < x2; j++) {
                for (int k = y1; k < y2; k++) {
                    if (i == 0) {
                        arr[j][k] += 1;
                    } else {
                        arr[j][k] += 2;
                    }
                }
            }
        }
        int minX = MAX_SIZE, maxX = 0, minY = MAX_SIZE, maxY = 0;
        boolean isExist = false;
        for (int i = 0; i <= MAX_SIZE; i++) {
            for (int j = 0; j <= MAX_SIZE; j++) {
                if (arr[i][j] == 1) {
                    isExist = true;
                    minX = Math.min(minX, i);
                    maxX = Math.max(maxX, i);
                    minY = Math.min(minY, j);
                    maxY = Math.max(maxY, j);
                }
            }
        }
        if (isExist) {
            System.out.println((maxX - minX + 1) * (maxY - minY + 1));
        } else {
            System.out.println(0);
        }
    }
}