LeetCode - 사각형 영역
15924 단어 algorithmsprogrammingjavascriptgo
문제 설명
2D 평면에서 두 직선 사각형의 좌표가 주어지면 두 사각형이 차지하는 총 면적을 반환합니다.
첫 번째 사각형은 왼쪽 아래 모서리(ax1, ay1)와 오른쪽 위 모서리(ax2, ay2)로 정의됩니다.
두 번째 사각형은 왼쪽 아래 모서리(bx1, by1)와 오른쪽 위 모서리(bx2, by2)로 정의됩니다.
문제 진술 출처: https://leetcode.com/problems/rectangle-area
예 1:
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
예 2:
Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 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
설명
이 문제에 대한 해결책은 간단합니다. 우리는 두 직사각형의 넓이를 구하기 위해 학교 수학 개념을 사용할 필요가 있습니다.
area = Area of rectangle 1 + Area of rectangle 2 - Area of intersecting portion
교차하는 부분의 면적을 계산하려면 다음 네 가지 좌표를 계산해야 합니다.
maxCommonX = max(ax1, bx1)
maxCommonY = max(ay1, by1)
minCommonX = min(ax2, bx2)
minCommonY = min(ay2, by2)
commonArea = (minCommonX - maxCommonX) * (minCommonY - maxCommonY)
알고리즘을 확인해 봅시다.
// compute the area of rectangles using L * H
- set area1 = (ax2 - ax1) * (ay2 - ay1)
set area2 = (bx2 - by1) * (by2 - by1)
// if the rectangles do not intersect, return area1 + area2
- if bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1
- return area1 + area2
- set maxCommonX = max(ax1, bx1)
set maxCommonY = max(ay1, by1)
- set minCommonX = min(ax2, bx2)
set minCommonY = min(ay2, by2)
- return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY);
C++, Golang, Javascript에서 알고리즘을 확인해 봅시다.
C++ 솔루션
class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int area1 = (ax2 - ax1) * (ay2 - ay1);
int area2 = (bx2 - bx1) * (by2 - by1);
if(bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1) {
return area1 + area2;
}
int maxCommonX = max(ax1, bx1);
int maxCommonY = max(ay1, by1);
int minCommonX = min(ax2, bx2);
int minCommonY = min(ay2, by2);
return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY);
}
};
골랑 솔루션
func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
area1 := (ax2 - ax1) * (ay2 - ay1)
area2 := (bx2 - bx1) * (by2 - by1)
if bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1 {
return area1 + area2;
}
maxCommonX := max(ax1, bx1)
maxCommonY := max(ay1, by1)
minCommonX := min(ax2, bx2)
minCommonY := min(ay2, by2)
return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
자바스크립트 솔루션
var computeArea = function(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
let area1 = (ax2 - ax1) * (ay2 - ay1);
let area2 = (bx2 - bx1) * (by2 - by1);
if(bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1) {
return area1 + area2;
}
let maxCommonX = Math.max(ax1, bx1);
let maxCommonY = Math.max(ay1, by1);
let minCommonX = Math.min(ax2, bx2);
let minCommonY = Math.min(ay2, by2);
return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY) ;
};
예제 1의 알고리즘을 시험 실행해 보겠습니다.
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Step 1: area1 = (ax2 - ax1) * (ay2 - ay1)
= (3 - -3) * (4 - 0)
= 6 * 4
= 24
area2 = (bx2 - bx1) * (by2 - by1)
= (9 - 0) * (2 - -1)
= 9 * 3
= 27
Step 2: if bx1 >= ax2 || bx2 <= ax1 || by1 >= ay2 || by2 <= ay1
0 >= 3 || 9 <= -3 || -1 >= 4 || 2 <= 0
false
Step 3: maxCommonX = max(ax1, bx1)
= max(-3, 0)
= 0
maxCommonY = max(ay1, by1)
= max(0, -1)
= 0
Step 4: minCommonX = min(ax2, bx2)
= min(3, 9)
= 3
minCommonY = min(ay2, by2)
= min(4, 2)
= 2
Step 5: return area1 + area2 - (minCommonX - maxCommonX) * (minCommonY - maxCommonY)
24 + 27 - (3 - 0) * (2 - 0)
51 - 3*2
51 - 6
45
We return the answer as 45.
Reference
이 문제에 관하여(LeetCode - 사각형 영역), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/_alkesh26/leetcode-rectangle-area-34ao텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)