Image Overlap

0과 1로 이루어진 벡터 두개를 받고 1번 벡터 데이터를 상하좌우로 이동했을 때,

2번 벡터와 가장 많이 중복되는 데이터를 구하는 문제이다.

다른 사람들은 빠른 속도를 내기위해서 비트 연산을 사용

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        
        vector<pair<int, int>> points1{};
        vector<pair<int, int>> points2{};

        int rowNum = img1.size();
        int colNum = img1[0].size();
        for (int i = 0; i < rowNum; i++)
        {
            for (int j = 0; j < colNum; j++)
            {
                if (img1[i][j])
                {
                    points1.push_back({i, j});
                }

                if (img2[i][j])
                {
                    points2.push_back({i, j});
                }
            }
        }

        map<pair<int, int>, int> differenceMap{};

        int points1Size = points1.size();
        int points2Size = points2.size();

        int maxOverlap{0};
        for (int i = 0; i < points1Size; i++)
        {
            for (int j = 0; j < points2Size; j++)
            {
                int differenceX{points1[i].first - points2[j].first};
                int differenceY{points1[i].second - points2[j].second};
                
                pair<int, int> point = {differenceX, differenceY};
                differenceMap[point]++;

                maxOverlap = std::max(maxOverlap, differenceMap[point]);
            }
        }

        return maxOverlap;
    }
};