[리트코드] 836 - Rectangle Overlap

836. Rectangle Overlap

Easy

---

An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the coordinate of its bottom-left corner, and (x2, y2) is the coordinate of its top-right corner. Its top and bottom edges are parallel to the X-axis, and its left and right edges are parallel to the Y-axis.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two axis-aligned rectangles rec1 and rec2, return true if they overlap, otherwise return false.

 

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Example 3:

Input: rec1 = [0,0,1,1], rec2 = [2,2,3,3]
Output: false

 

Constraints:

• rec1.length == 4
• rec2.length == 4
• -109 <= rec1[i], rec2[i] <= 109
• rec1 and rec2 represent a valid rectangle with a non-zero area.

분류

수학, 기하학

---

문제 풀이

문제 분석

이 문제는 두 개의 축에 정렬된(axis-aligned) 직사각형이 주어졌을 때, 이 두 직사각형이 서로 겹치는지 여부를 판단하여 True 또는 False를 반환하는 것입니다.

• 입력: rec1과 rec2라는 두 개의 리스트가 주어집니다. 각 리스트는 [x1, y1, x2, y2] 형식으로 직사각형을 나타냅니다.
  • (x1, y1)은 직사각형의 왼쪽 아래 모서리 좌표입니다.
  • (x2, y2)는 직사각형의 오른쪽 위 모서리 좌표입니다.
  • 직사각형의 변은 X축 또는 Y축에 평행합니다.
• 겹침의 정의: 두 직사각형의 교차 영역(intersection area)이 양수일 때만 겹친다고 간주합니다. 즉, 모서리나 변만 닿는 경우는 겹치는 것으로 보지 않습니다.
• 출력: 두 직사각형이 겹치면 True, 그렇지 않으면 False를 반환합니다.
• 제약 조건: 직사각형은 항상 유효하며, 면적이 0이 아닙니다. 좌표 값은 매우 클 수 있습니다 (10^9 범위).

접근 방법

이 문제를 해결하는 가장 직관적인 방법은 "두 직사각형이 겹치지 않는 경우"를 먼저 정의하고, 그 조건의 **논리적 부정(NOT)**을 취하는 것입니다. 겹치지 않는 조건을 직접 정의하는 것이 겹치는 조건을 직접 정의하는 것보다 일반적으로 더 쉽습니다.

두 직사각형이 겹치지 않는 경우는 다음과 같은 4가지 상황 중 하나라도 해당할 때입니다:

1. 하나의 직사각형이 다른 직사각형의 완전히 왼쪽에 있을 때.
2. 하나의 직사각형이 다른 직사각형의 완전히 오른쪽에 있을 때.
3. 하나의 직사각형이 다른 직사각형의 완전히 아래쪽에 있을 때.
4. 하나의 직사각형이 다른 직사각형의 완전히 위쪽에 있을 때.

문제에서 "모서리나 변만 닿는 경우는 겹치지 않는다"고 명확히 했으므로, 위 4가지 상황을 정의할 때 등호(=)를 포함하는 비교 연산자를 사용하면 됩니다. 예를 들어, rec1의 오른쪽 변이 rec2의 왼쪽 변과 같거나 더 왼쪽에 있다면, rec1은 rec2의 왼쪽에 있는 것으로 간주합니다.

이 4가지 조건 중 어느 하나라도 참이면 두 직사각형은 겹치지 않습니다. 따라서 이 4가지 조건을 OR로 묶고 전체에 NOT을 적용하면, 직사각형이 겹치는 조건이 됩니다.

구현 설명

주어진 코드는 겹치지 않는 조건의 논리적 부정을 이용하여 겹치는 조건을 직접 계산합니다.

단계 1: 직사각형 좌표의 의미 파악

• rec1[0]은 첫 번째 직사각형의 왼쪽 X 좌표 (x1_1)
• rec1[1]은 첫 번째 직사각형의 아래 Y 좌표 (y1_1)
• rec1[2]은 첫 번째 직사각형의 오른쪽 X 좌표 (x2_1)
• rec1[3]은 첫 번째 직사각형의 위 Y 좌표 (y2_1)
• rec2도 동일한 방식으로 x1_2, y1_2, x2_2, y2_2 좌표를 가집니다.

단계 2: X축을 기준으로 겹치지 않는 조건 정의 및 그 부정

• 겹치지 않는 X축 조건:
  • rec1이 rec2의 왼쪽에 완전히 있는 경우: rec1[2] <= rec2[0] (즉, rec1의 오른쪽 X좌표가 rec2의 왼쪽 X좌표보다 작거나 같을 때)
  • rec1이 rec2의 오른쪽에 완전히 있는 경우: rec1[0] >= rec2[2] (즉, rec1의 왼쪽 X좌표가 rec2의 오른쪽 X좌표보다 크거나 같을 때)
• 겹치는 X축 조건 (겹치지 않는 조건의 부정):
  • (rec1[2] > rec2[0]) AND (rec1[0] < rec2[2])
  • 이것은 rec1이 rec2의 왼쪽에 있지도 않고 오른쪽에 있지도 않은 상태, 즉 X축 상에서 두 직사각형의 X-범위가 서로 교차하는 경우를 의미합니다. '>와 <`를 사용하여 경계가 닿는 경우는 겹치지 않도록 처리합니다.

단계 3: Y축을 기준으로 겹치지 않는 조건 정의 및 그 부정

• 겹치지 않는 Y축 조건:
  • rec1이 rec2의 아래에 완전히 있는 경우: rec1[3] <= rec2[1] (즉, rec1의 위 Y좌표가 rec2의 아래 Y좌표보다 작거나 같을 때)
  • rec1이 rec2의 위에 완전히 있는 경우: rec1[1] >= rec2[3] (즉, rec1의 아래 Y좌표가 rec2의 위 Y좌표보다 크거나 같을 때)
• 겹치는 Y축 조건 (겹치지 않는 조건의 부정):
  • (rec1[3] > rec2[1]) AND (rec1[1] < rec2[3])
  • 이것은 rec1이 rec2의 아래에 있지도 않고 위에 있지도 않은 상태, 즉 Y축 상에서 두 직사각형의 Y-범위가 서로 교차하는 경우를 의미합니다. 마찬가지로 '>와 <`를 사용하여 경계가 닿는 경우는 겹치지 않도록 처리합니다.

단계 4: 최종 겹침 여부 판단

• 두 직사각형이 실제로 겹치려면, X축 상에서도 겹쳐야 하고 동시에 Y축 상에서도 겹쳐야 합니다.
• 따라서 코드의 최종 반환 값은 X축 겹침 조건 2가지와 Y축 겹침 조건 2가지를 모두 and 연산으로 연결한 결과입니다: rec1[0] < rec2[2] (rec1_x1 < rec2_x2) and rec1[2] > rec2[0] (rec1_x2 > rec2_x1) and rec1[1] < rec2[3] (rec1_y1 < rec2_y2) and rec1[3] > rec2[1] (rec1_y2 > rec2_y1)
• 이 네 가지 조건이 모두 참일 때만 True를 반환하고, 하나라도 거짓이면 False를 반환합니다.

⏱복잡도 분석

• 시간 복잡도: O(1)
  • 이 코드는 직사각형의 좌표 값을 사용하여 몇 번의 상수 시간 비교 연산 (<, >)과 논리 연산 (and)만 수행합니다. 입력 직사각형의 크기나 좌표 값의 범위에 관계없이 항상 일정한 시간이 소요되므로, 시간 복잡도는 O(1)입니다.
• 공간 복잡도: O(1)
  • 코드는 입력으로 받은 두 직사각형 외에 추가적인 자료 구조를 생성하거나 저장 공간을 사용하지 않습니다. 몇 개의 임시 변수만 사용하므로, 공간 복잡도는 O(1)입니다.

핵심 포인트

1. 겹치지 않는 조건의 부정 활용: 기하학 문제에서 직접 겹치는 조건을 찾는 것보다 겹치지 않는 조건(분리 조건)을 정의하고 그 부정(NOT)을 취하는 것이 더 간결하고 오류가 적은 접근 방식입니다.
2. 축 단위 분리 및 결합: 직사각형 겹침 문제는 X축에서의 겹침 여부와 Y축에서의 겹침 여부를 독립적으로 판단한 후, 두 결과를 논리곱(AND)으로 결합하여 최종 결과를 얻는 방식으로 해결할 수 있습니다.
3. 경계 포함 여부의 정확한 처리: 문제에서 "교차 영역이 양수일 때"만 겹친다고 정의했으므로, 직사각형들이 변이나 모서리에서만 닿는 경우는 겹치지 않아야 합니다. 이를 위해 비교 연산자 선택에 주의해야 하며, 등호(=)를 포함하지 않는 > 또는 < 연산자를 사용하여 정확한 겹침을 판단해야 합니다.

풀이 코드

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        return rec1[0]< rec2[2] and rec1[2] > rec2[0] and rec1[1] < rec2[3] and rec1[3] > rec2[1]