Detect Squares

2013. Detect Squares

class DetectSquares {
    map<int, int> mp;
public:
    DetectSquares() {
        
    }
    
    void add(vector<int> point) {
        mp[point[0]<<10 | point[1]]++;
    }
    
    int count(vector<int> point) {
        int result = 0;
        auto x = point[0], y = point[1];
        for (auto [p, c]: mp) {
            int cx = p >> 10, cy = p & 1023;
            if (cx != x && cy != y && abs(cx - x) == abs(cy - y)) {
                result += mp[cx<<10 | y] * mp[x<<10 | cy] * c;
            }
        }
        return result;
    }
};

add 로 점의 위치와 개수를 저장 count 에서는 저장된 위치와 주어진 위치가 대각선상에 있을 경우 정사각형을 만들수 있으므로, 두 점을 잇는 선분을 정사각형의 대각선으로 가정하고 나머지 두 점의 위치를 구하고, 해당 점이 add 에 추가 되어있는 경우 각 위치의 점의 개수를 모두 곱하면 사각형을 만들수 있는 경우의 수가 나온다.

unordered_map 으로 하면 collision 나서 일부 TC 가 fail 난다.
hash 를 정의하 면pass 할수도 있을거 같은데, 일부러 collision TC 를 만들면 어떻게 방법이 없다.

n == add(), count() called count,

Time:

• add(): O(log(n))
  • map 에 값 insert 하는 시간 log(n)
• count(): O(n·log(n))
  • map 순회(O(n)) 하면서 map 의 값 find(log(n)) 하는 시간 n·log(n)

Space: O(n)
map 의 크기 n