[LeetCode] 2661. First Completely Painted Row or Column

https://leetcode.com/problems/first-completely-painted-row-or-column/description/

leetcode - First Completely Painted Row or Column

문제 유형: 행렬, 구현, 시뮬레이션

문제 난이도: Medium

 

문제

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

 

0-indexed의 정수 배열 arr이 주어진다. m x n의 정수 행렬 mat이 주어진다.

각 셀들은 [1, m*n]의 범위에서 하나씩 수를 가진다.

arr의 수들을 인덱스 i로 하나씩 읽어서 해당 숫자를 가진 셀을 색칠할것이다.

한 행이나 열이 색칠되는 최소의 i를 구하시오.

 

풀이

내 개인적인 선호상, 나는 n x m으로 하였다.

rows[i] = i행에 남은 색칠해야 할 셀의 개수이다. m으로 초기화한다.

cols[j] = j행에 남은 색칠해야 할 셀의 개수이다. n으로 초기화한다.

pos배열에 {소속된 행, 소속된 열}을 미리 구해놓는다.

 

그 뒤, arr을 읽으면서 rows[소속된행]에 1을 빼고 만약 0이 된다면 i를 반환한다.

cols[소속된열]에 1을 빼고 만약 0이 된다면 i를 반환한다.

 

코드

C++

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        int l = arr.size();
        vector<int> rows(n, m);
        vector<int> cols(m, n);
        vector<pair<int, int>> pos(m*n+1);

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                pos[mat[i][j]] = make_pair(i, j);
            }
        }

        // paint..
        for(int i = 0; i < l; ++i) {
            int k = arr[i];
            if(--rows[pos[k].first] == 0) return i;
            if(--cols[pos[k].second] == 0) return i;
        }
        return -1;
    }
};