[Leetcode/Python] 223. Rectangle Area

문제 링크

Rectangle Area - LeetCode

 

문제 설명

2D 평면에서 두 직선 사각형의 좌표가 주어지면 두 사각형이 차지하는 총 면적을 반환합니다.

첫 번째 사각형은 왼쪽 아래 모서리(ax1, ay1)와 오른쪽 위 모서리(ax2, ay2)로 정의됩니다.
두 번째 사각형은 왼쪽 아래 모서리(bx1, by1)와 오른쪽 위 모서리(bx2, by2)로 정의됩니다.

.

간단히 이런 식으로 도형이 그려지고 색칠된 부분의 넓이를 구하면 된다.

입출력 예시

입력	출
ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2	45
ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2	16

 

제한 사항

 

• -10^4 <= ax1 <= ax2 <= 10^4
• -10^4 <= ay1 <= ay2 <= 10^4
• -10^4 <= bx1 <= bx2 <= 10^4
• -10^4 <= by1 <= by2 <= 10^4

 

문제 풀이

 먼저 두 도형의 넓이를 구하는 것은 어렵지 않다. 문제는 두 도형이 겹치는 부분이 얼마나 되는지를 찾아야 한다.

 

 일단 필자의 풀이는 a와 b의 넓이를 구하고 겹치는 부분을 빼는 방법을 택했다. 그리고 겹치는 부분의 넓이를 구하고 이 값을 빼면 된다.

 

 문제가 클래스로 주어졌기에 각 함수의 설명을 달고자 한다.

 

• computeArea : 문제의 정답을 구하는 함수, 총 면적을 구해준다.
• __getArea (private) : 도형의 넓이를 구하는 함수
• __getOverlapSegmentLength : 겹치는 구간의 선분 길이를 구해주는 함수. 가장 중요한 함수다.

여기서 __getOverlapSegmentLength 만 이해하면 이 문제를 다 푼거라 봐도 된다.

 

먼저 겹치는 부분의 x축의 길이와 y축의 길이를 구하는 방법은 같다. 그리고 겹치는 경우는 다음 세가지가 존재한다.

 

1. a1과 a2가 모두 b1, b2 사이에 있을 경우
2. b1과 b2가 모두 a1, a2 사이에 있을 경우
3. a1 < b1 < a2 이면서 a2 < b2 거나, a1 < b2 < a1 이면서 b1 < a1 인 경우

이 세가지를 만족하지 않는다면, 겹치는 부분이 존재하지 않으므로 0을 출력한다.

 

소스코드

class Solution:
    def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
        a = self.__getArea(ax1, ax2, ay1, ay2)
        b = self.__getArea(bx1, bx2, by1, by2)
        innerX = self.__getOverlapSegmentLength(ax1, ax2, bx1, bx2)
        innerY = self.__getOverlapSegmentLength(ay1, ay2, by1, by2)
        print(innerX, innerY)
        inner = innerX * innerY
        return a + b - inner
    
    def __getArea(self, x1: int, x2: int, y1: int, y2: int) -> int:
        x = x2 - x1
        y = y2 - y1
        return x * y

    def __getOverlapSegmentLength(self, a1: int, a2: int, b1: int, b2: int) -> int:
        if a1 <= b1 and b1 <= a2:
            if b2 <= a2:
                return b2 - b1
            else:
                return a2 - b1
        elif a1 <= b2 and b2 <= a2:
            return b2 - a1
        elif b1 <= a1 and a1 <= b2:
            return a2 - a1
        return 0

 

 

코딩 테스트, 어떻게 대비해야 할까?