[LeetCode] 2661. First Completely Painted Row or Column (Python)

 

 

난이도: 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.

 

문제 예제

---

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].

 

제한 사항

---

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

 

Solution(솔루션)

---

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])

        row = [0 for _ in range(n)]
        col = [0 for _ in range(m)]

        xy = [0 for _ in range(n*m+1)]

        for i in range(n):
            for j in range(m):
                xy[mat[i][j]] = (i, j)

        for i in range(n*m+1):
            x, y = xy[arr[i]]
            row[x] += 1
            col[y] += 1
            if row[x] == m or col[y] == n:
                return i

 

먼저 row와 column이 얼마나 paint됐는지 저장할 수 있는 row와 col 리스트를 만들었다.

 

다음으로, mat에 있는 숫자들의 좌표값을 저장했다.

 

이제 arr의 숫자들을 순서대로 탐색해 그 숫자의 저장해놓은 좌표를 가져왔고, 이 숫자가 속해 있는 row와 col에 +1을 해주었다.

 

이 때 row 또는 col이 완벽하게 paint 되었다고 하면 즉 row[x] == m 또는 col[y] == n을 만족하면 현재 i를 return 하여 정답을 맞출 수 있었다.

 

---

문제: 2661. First Completely Painted Row or Column

 

깃허브: github

algorithmPractice/LeetCode/2685-first-completely-painted-row-or-column at main · laewonJeong/algorithmPractice