🧾 문제 설명

n × n 크기의 격자가 있음.
격자의 원점(0,0)은 왼쪽 아래 모서리에 위치함.

rectangles라는 2차원 정수 배열이 주어짐.
rectangles[i] = [startx, starty, endx, endy]는 i번째 직사각형의 좌표를 나타냄.

• (startx, starty)는 직사각형의 왼쪽 아래 꼭짓점
• (endx, endy)는 직사각형의 오른쪽 위 꼭짓점
• 직사각형들은 서로 겹치지 않음

---

🎯 목표

두 개의 수평선 또는 두 개의 수직선으로 격자를 잘라서,
총 3개의 섹션으로 만들 수 있는지 판단하라.
단, 아래 조건을 모두 만족해야 함:

1. 각 섹션마다 적어도 하나 이상의 직사각형이 있어야 함
2. 모든 직사각형은 오직 하나의 섹션에만 속해야 함 (겹치지 않아야 함)

---

✅ 반환값

• 위 조건을 만족하는 절단이 가능하면 true, 아니면 false를 반환

---

💡 예시

예제 1:

입력: n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
출력: true

설명: y = 2, y = 4에서 수평으로 자르면 3개의 구역이 되고,
각 구역에 적어도 하나의 직사각형이 포함됨.

---

예제 2:

입력: n = 4, rectangles = [[0,0,1,1],[2,0,3,4],[0,2,2,3],[3,0,4,3]]
출력: true

설명: x = 2, x = 3에서 수직으로 자르면 조건 만족

---

예제 3:

입력: n = 4, rectangles = [[0,2,2,4],[1,0,3,2],[2,2,3,4],[3,0,4,2],[3,2,4,4]]
출력: false

설명: 어떤 두 수평선 또는 수직선을 선택해도 조건을 만족할 수 없음

---

📌 제한 사항

• 3 ≤ n ≤ 10⁹
• 3 ≤ rectangles.length ≤ 10⁵
• 0 ≤ startx < endx ≤ n
• 0 ≤ starty < endy ≤ n
• 직사각형들은 서로 겹치지 않음

1. 풀이

$O(NLogN)$

import java.util.Arrays;

class Solution {
    public boolean checkValidCuts(int n, int[][] rectangles) {
        // x축 기준 범위가 겹치는 사각형을 모두 포함하는 가장 큰 사각형을 만들어서 그 사각형이 몇 개 나오는지 개수를 세면 된다.
        Arrays.sort(rectangles, (a, b) -> a[0] - b[0]);
        int xSection = countSection(rectangles, true);

        // y축 기준 범위가 겹치는 사격형을 모두 포함하는 가장 큰 사각형을 만들어서 그 사각형이 몇 개 나오는지 개수를 세면 된다.
        Arrays.sort(rectangles, (a, b) -> a[1] - b[1]);
        int ySection = countSection(rectangles, false);
        System.out.println(xSection + " " + ySection);
        if (xSection > 2 || ySection > 2)
            return true;
        return false;
    }

    public int countSection(int[][] rectangles, boolean xAxis) {
        int axis = 0;
        if (!xAxis)
            axis = 1;
        int sections = 0;
        int startX = rectangles[0][axis];
        int endX = rectangles[0][axis + 2];

        for (int[] rectangle: rectangles) {
            // 사각형의 x 범위가 겹치는 경우
            if (endX > rectangle[axis]) {
                // 더 큰 사각형으로 업데이트
                endX = Math.max(endX, rectangle[axis + 2]);
            }
            // 사각형의 x 범위가 겹치지 않는 경우
            else {
                // 섹션의 개수를 증가시키고, 현재 사각형을 포함하는 새로운 사각형 만들기
                sections++;
                startX = rectangle[axis];
                endX = rectangle[axis + 2];
            }
        }
        sections++;
        return sections;
    }
}