[HashMap/Set][Medium] 2352. Equal Row and Column Pairs

https://leetcode.com/problems/equal-row-and-column-pairs/description

Equal Row and Column Pairs - LeetCode

 

Q. 해당 모든 행의 값들 순서와 해당 모든 열의 순서가 같을때, 이 열과 행을 같다라고 한다.
      input grid에서 같은 열과 행의 조합의 수를 반환하라.

 

Solution. 각 행과 열을 hash로 비교할 수 있는 상태로 만들고(여기서는 string) 이를 이용해 같은 지 비교하는 방식을 사용.

 string key를 만들기 위해 input grid만큼 연산을 해야만 한다. TC => O(MxN) 

 다만, input이 숫자 값이므로, 그냥 int를 string변환하면, 11,22,33 과 1,122,33 이 같게 판단되므로, 이것에만 유의하자. 

 

 frequency hash를 이용하여 문제 푸는 것에 익숙하다면 쉬운 문제.

 

int equalPairs(vector<vector<int>>& grid)
{
    map<string, int> mapFreq;
    for (int k = 0; k < grid.size(); ++k)
    {
        string line = "";
        for (int x = 0; x < grid[0].size(); ++x)
        {
            line += to_string(grid[k][x]);
            line += "_";	// 구분자를 하나씩 넣어 준다. 뭐든 관계 없음.
        }

        mapFreq[line]++;
    }

    int ret = 0;
    for (int k = 0; k < grid[0].size(); ++k)
    {
        string line = "";
        for (int x = 0; x < grid.size(); ++x)
        {
            line += to_string(grid[x][k]);
            line += "_";
        }

        if (mapFreq.find(line) != mapFreq.end())
            ret += mapFreq[line];
    }
    return ret;
}