[LeetCode] 850. Rectangle Area II

문제 출처: https://leetcode.com/problems/rectangle-area-ii/

Rectangle Area II - LeetCode

---

문제

각 축을 기준으로 정렬된 rectangles 배열이 주어진다. 각 rectangles[i] = [x_i1, y_i1, x_i2, x_i2]는 (x_i1, y_i1)이 i^th 사각형의 왼쪽 하단 좌표이고, (x_i2, y_i2)는 i^th 사각형의 우측 상단 좌표이다.

 

평면상에서 사각형으로 덮여있는 영역의 수를 찾아라. 답이 매우 클 수 있기때문에 10⁹+7로 나눈 나머지를 반환하라.

예제

 

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6

Explanation: As illustrated in the picture.

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49

Explanation: The answer is 1018 modulo (10^9 + 7), which is (10^9)2 = (-7)2 = 49.

---

풀이

x 좌표를 슬라이딩하면서 현재 x 좌표에 몇 개의 사각형이 관여되어 있는지 계산하는 방식을 사용하였다.

 

rectangles[i] = [x_i1, y_i1, x_i2, x_i2] 라면, 이 사각형은 x좌표를 기준으로 x_i1에서 x_i2까지 존재함을 알 수 있다. 이때 다른 사각형이 관여하지 않는다는 조건이라면 x_i1 ~ x_i2 의 모든 좌표에서 각각 (y_i2 - y_i1)개의 사각형이 존재할 것이다.

 

위와 같이 x좌표를 기준으로 사각형을 생각하기 위해서, 주어지는 rectangles[i] = [x_i1, y_i1, x_i2, y_i2] 를 [x, recType, y_i1, y_i2]와 같은 형태로 분해한다(x = x_i1 또는 x_i2, recType=0 또는 1). 여기서 recType=0 이라면 사각형이 시작됨을 의미하고, recType=1이라면 사각형의 끝을 의미한다.

 

또한 현재 x좌표에 관여하는 사각형이 어떤 것이 있는지 확인하기 위해서 active라는 배열을 사용할 것이다.

 

현재까지의 내용을 코드화 시키면 아래와 같다. 아직까지는 채워야 하는 내용이 많다.

var rectangleArea = funciton(rectangles) {

    var events = [];
    for (const [x1, y1, x2, y2] of rectangles) {
    	events.push([x1, 0, y1, y2]);	// 0: 사각형 시작
        events.push([x2, 1, y1, y2]);	// 1: 사각형 끝
    }
	
    // x 좌표를 기준으로 정렬
    events.sort((a, b) => a[0] - b[0]);
    
    var active = [];
    for (const [x, recType, y1, y2] of events) {
    	// TODO1: 현재 x 좌표에서 몇 개의 사각형이 커버되는지 카운트
        // TODO2: recType에 따른 active배열 업데이트
    }
}

위 코드에 주석으로 작성되어 있는 TODO 리스트의 항목을 순차적으로 완성시켜보자.

 

TODO 1: 현재 x 좌표에서 몇 개의 사각형이 있는가.

 

현재 x좌표에 관여하고 있는 사각형이 어떤 것이 있는지 보기 위해서는 미리 정의해놓은 active 배열을 순회하면 된다. active 배열의 업데이트는 이후 TODO 2에서 작성할 거지만, active 배열은 아래와 같은 규칙을 따르게 만들 것이다.

• active[i] = [y1, y2] (y1 < y2)
• active는 y1을 기준으로 정렬되어 있는 배열

 

이런 규칙을 따르는 active 배열을 통해 아래의 그림과 같은 연산을 수행할 수 있다. 

var rectangleArea = funciton(rectangles) {

    var events = [];
    for (const [x1, y1, x2, y2] of rectangles) {
    	events.push([x1, 0, y1, y2]);	// 0: 사각형 시작
        events.push([x2, 1, y1, y2]);	// 1: 사각형 끝
    }
	
    // x 좌표를 기준으로 정렬
    events.sort((a, b) => a[0] - b[0]);
    
    let ans = 0;
    let prevX = events[0][0];
    const active = [];
    for (const [x, recType, y1, y2] of events) {
    	// TODO1: 현재 x 좌표에서 몇 개의 사각형이 커버되는지 카운트
        let coverddY = 0;
        let tempRectCount = 0;
        for (const [ay1, ay2] of active) {
            coverddY = Math.max(coverddY, ay1);		// acitve[i]의 범위 중, 카운트 안된 y 위치 계산
            tempRectCount += Math.max(0, ay2 - coverddY);// 사각형 개수 계산하여 합산
            coverddY = Math.max(coverddY, ay2);		// 카운트 된 y 위치 업데이트
        }
        
        ans += tempRectCount * (x - prevX)
        
        // TODO2: recType에 따른 active배열 업데이트
    }
}

 

TODO 2: active 배열 관리

 

active 배열 관리는 recType에 따라 수행한다.

• recType=0이라면, 단순하게 [y1, y2]를 active에 추가하고 y1을 기준으로 정렬해주면 된다.
• recType=1이라면, active배열 안에서 [y1, y2]의 값을 찾아서 제거하는 과정이 필요하다.

var rectangleArea = funciton(rectangles) {

    var events = [];
    for (const [x1, y1, x2, y2] of rectangles) {
    	events.push([x1, 0, y1, y2]);	// 0: 사각형 시작
        events.push([x2, 1, y1, y2]);	// 1: 사각형 끝
    }
	
    // x 좌표를 기준으로 정렬
    events.sort((a, b) => a[0] - b[0]);
    
    let ans = 0;
    let prevX = events[0][0];
    const active = [];
    for (const [x, recType, y1, y2] of events) {
    	// TODO1: 현재 x 좌표에서 몇 개의 사각형이 커버되는지 카운트
        let coveredY = 0;
        let tempRectCount = 0;
        for (const [ay1, ay2] of active) {
            coveredY = Math.max(coveredY, ay1);
            tempRectCount += Math.max(0, ay2 - coveredY);
            coveredY = Math.max(coveredY, ay2);
        }
        
        ans += tempRectCount * (x - prevX);
        
        // TODO2: recType에 따른 active배열 업데이트
        if (recType) {
            active.push([y1, y2]);
            active.sort((a, b) => a[0] - b[0]);
        } else {
            for (let i = 0; i < active.length; i++) {
            	if (active[i][0] == y1 && active[i][1] == y2) { active.splice(i, 1); break; }
            }
        }
        
        prevX = x;
    }
    
    return ans;
}

 

 

※ 위 코드는 modulo 10⁹ + 7 을 적용하지 않은 것으로, leetcode에 제출하기 위해서는 modulo를 적용해야 함

 

Github: 850.js

GitHub - opwe37/Algorithm-Study