2661. First Completely Painted Row or Column

https://leetcode.com/problems/first-completely-painted-row-or-column/description/?envType=daily-question&envId=2025-01-20

 

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.

 

Example 1:

Input: arr = [1,3,4,2],
mat = [[1,4],[2,3]]

Output: 2 Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

 

 

Example 2:

Input: arr = [2,8,7,4,1,3,5,6,9],
mat = [[3,2,5],[1,4,6],[8,7,9]]

Output: 3 Explanation: The second column becomes fully painted at arr[3].

 

 

Constraints:

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= arr[i], mat[r][c] <= m * n
• All the integers of arr are unique.
• All the integers of mat are unique.

 

arr에 있는 원소를 순회하면서, mat에 있는 원소들 중 하나의 행 혹은 열이 모두 방문 처리가 되었을 때의 최소 index를 리턴하는 문제였다.

 

어떻게 접근할 수 있을까? 가장 생각나는대로 접근을 하자면 arr 원소를 순회할 때 mat을 순회하며 방문처리를 해주고, 행 혹은 열이 모두 방문처리 됐을 때 index를 리턴하는 방법이다. 하지만, 그렇게 했을 때 시간복잡도는 arr.length * mat.length * mat[0].lenght = 10^5 * 10^5가 되기 때문에 시간 초과가 생길 것이다.

 

따라서, 2차원 배열에서 원하는 값에 접근을 하기 위해선 탐색 속도가 빠른 자료구조가 필요했다.

해쉬맵을 사용하면, key에 해당하는 value를 O(1)에 찾을 수 있다. 따라서, 나는 [mat 배열의 값, 좌표위치] 형태로 해쉬맵을 선언해 주었다.

Map<Integer, int[]> map = new HashMap<>();

 

처음에 mat에 해당하는 모든 값과 좌표를 저장해준 다음, 이제 arr를 순회하면서 해당 열이나 행의 방문처리를 확인해 주어야 한다.

 

이것을 확인해주기 위해 각 row, col의 상태 여부를 나타내는 1차원 배열을 선언해주었다.

int m = mat.length;
int n = mat[0].length;

int [] rowCnt = new int[m];
int [] colCnt = new int[n];

 

선언하고 나서 값을 할당해 주어야 하는데, rowCnt에는 행의 값인 n으로 채우고, colCnt에는 열의 값인 m으로 채워야 한다. 

나는 반대로 생각했고, 처음엔 왜 이렇게 해주는지 이해가 잘 가지 않았다.

4	3	5
1	2	6

 

해당 케이스를 생각해보자.

rowCnt = new int[3], colCnt = new int[2]; 가 될 것이다.

 

rowCnt는 3개가 있기 때문에 col의 상태 여부를 추적할 것이고,

colCnt는 2개가 있기 때문에 row의 상태 여부를 추적할 것이다.

 

따라서, rowCnt엔 모든 값을 2로 채우고, colCnt엔 모든 값을 3으로 채워줬다. 

 

이렇게 arr를 순회하며 각 row와 col값을 -1 시켜주고, 둘 중에 하나라도 0이 되는 순간이 있다면 문제 조건에 성립하기 때문에 인덱스를 리턴해주면 된다.

 

정답 코드

class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int len = arr.length;

        Map<Integer, int[]> map = new HashMap<>();
        int [] rowCnt = new int[m];
        int [] colCnt = new int[n];

        Arrays.fill(rowCnt, n);
        Arrays.fill(colCnt, m);

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                map.put(mat[i][j], new int[]{i,j});
            }
        }

        for(int i = 0; i < len; i++) {
            int [] pos = map.get(arr[i]);
            int x = pos[0];
            int y = pos[1];
            rowCnt[x]--;
            colCnt[y]--;

            if (rowCnt[x] == 0 || colCnt[y] == 0) {
                return i;
            }
        }
        return -1;
    }
}

 

key points

1. 시간 복잡도를 어떻게 줄일 수 있는지 -> 자료구조 map 사용
2. row와 col의 방문처리를 추적할 수 있는 1차원 배열을 선언