[c++/LeetCode-Hash Table] 939. Minimum Area Rectangle

 

 

 

 

난이도: Medium

키워드: Hash Table

 

 

 

🎲 문제

X-Y 평면상의 점들의 배열 points가 주어졌습니다. 여기서 points[i] = [xi, yi]입니다.
이러한 점들로 형성된 X축과 Y축에 평행한 직사각형의 최소 면적을 반환합니다. 만약 그러한 직사각형이 없다면, 0을 반환합니다.

 

문제 원문: https://leetcode.com/problems/minimum-area-rectangle/description/

 

Example 1:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

 

🎲  문제 풀이

만들 수 있는 사각형을 탐색하면서 사각형들 중 최소 면적 값을 구하고자한다.

이를 위해서 두 개의 점이 주어졌을 때 이 두 점 외에 사각형을 만들 수 있는 점들이 존재하는 지 O(1) 으로 탐색하는 형태로 사각형 면적을 구할 수 있다.

 

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {

        unordered_map<int, set<int>> hash;
        for(auto point : points){
            auto x = point[0], y = point[1];
            hash[x].insert(y);
        }

        int MAX = 16 * pow(10, 8);
        int ans = MAX;

        for(auto i=0; i < points.size()-1; ++i){
            for(auto j=i; j < points.size(); ++j){
                auto x1 = points[i][0], y1 = points[i][1];
                auto x2 = points[j][0], y2 = points[j][1];

                if(x1 == x2) continue;
                if(y1 == y2) continue;

                // check rectangle
                if(hash[x1].find(y2) != hash[x1].end() && hash[x2].find(y1) != hash[x2].end())
                    ans = min(ans, abs(x1-x2) * abs(y1-y2));
            }
        }

        if(ans == MAX)
            ans = 0;

        return ans;
        
    }
};

 

 

해당 채널에서 Leet Code 해설해 놓은 것들이 있는데 과정이 체계적이고 좋은 것 같다 :)  

https://youtu.be/xvuuENPhEH4?feature=shared