[LeetCode] 223. Rectangle Area

문제 URL : https://leetcode.com/problems/rectangle-area/

Rectangle Area - LeetCode

 

문제 접근법 : 

좌상단 우하단 의 좌표로 사각형을 만들어 2개의 사각형이 주어졌을때 좌표에서 색칠한 부분의 넓이를 구하는문제입니다.

 

이문제를 풀고 제가 잘못 생각하고있던 이론을 발견하고 다시 공부하게 된 문제네요

솔직히 금방 풀거라생각했습니다. 두사각형의 겹쳐있다면 4개의 점중에 하나가 다른사각형에 안에 있다고 생각하고 코드를 고치면서 풀었는데 2시간가까이 2900 개정도의 테스트케이스는 통과하고 더이상 통과를 안하더군요

 

완전히 잘못된 이론이더군요 사각형과 점과의 관계면 성립하겠지만 사각형과 사각형의 관계에서는 안되는 조건이라는걸

깨닫는순간  벙쪘습니다.

 

솔직히 답을보고  그림을 다시 그리고 충돌되지 않는 조건만 따져서 결국 풀어냈습니다.

 

 

 

 

이런식의 그림을 그릴때 절대로 사각형이 겹치지 않을려면 하나의 사각형이 우상단의 좌표가 좌상단의 좌표가 커야하거나

좌상단의 좌표가 우상단의 좌표보다 커야하는 조건일경우 겹치지 않더군요

 

 

그렇다면 겹칠때는 겹친부분의 좌표는 어떻게 구하냐?

 

그림을 보면 새로운 사각형엔 좌상단은 좌상단끼리 우하단은 우하단끼리 연관이 됩니다.

즉 좌상단은 큰값을 기준으로 우하단은 작은값을 기준으로 겹치는 사각형이 만들어집니다.

 

소스코드 :

 

class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
    int r1 = (ax2-ax1)*(ay2-ay1);
    int r2 = (bx2-bx1)*(by2-by1);
    int sub = (min(ax2,bx2)-max(ax1,bx1))*(min(ay2,by2)-max(ay1,by1));
    if(ax2<bx1 || bx2<ax1||ay2<by1||by2<ay1) return r1+r2;
    return r1+r2-sub;
}
};

 

쉽다고 생각했고 당연하게 알고있을거라 생각했떤 문제였지만 내가 잘못된 지식을 갖고있었다는것을 다시한번 깨닫게 되더군요 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.