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.
또 좀 복잡해 보이는 Matrix 문제다.
Matrix 문제역시 언젠가는 잘 다뤄야 하는 영역이니까 함 풀어보자
문제 이해는 쉽다. 그냥 1 Bingo 찾으면 끝난다는 것이다.
1. Python
적절히 잘 한 거 같은데 -_- 시간초과가 떴다 짜증나게 ㅠㅠ
시간초과도 괜찮으니까 일단 논리적으로 코드가 맞냐 안 맞냐는 알려줬으면 좋겄네
class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
m = len(mat)
n = len(mat[0])
# m * n Matrix
visited = [ [False] * n for _ in range(m) ]
def bingo(temp:list[list[int]]) -> bool :
# row check
for row in range(m):
if False not in temp[row]:
return True
# column check
for col in range(n):
row_col = []
for row in range(m):
row_col.append(temp[row][col])
if False not in row_col :
return True
return False
for val in arr:
for i in range(m):
for j in range(n):
if mat[i][j] == val :
visited[i][j] = True
break
if bingo(visited): return arr.index(val)
내가 봐도 bingo check 하는 부분에서 시간을 많이 쓸 거 같긴 하더라..
Hash Map을 쓰면 Time complexity를 줄일 수 있다.
class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
# Map values in mat to their (row, column) indices
val_to_pos = {mat[i][j]: (i, j) for i in range(m) for j in range(n)}
# Arrays to track painted cells in each row and column
row_count = [0] * m
col_count = [0] * n
for i, val in enumerate(arr):
# Find the position of the current value in mat
row, col = val_to_pos[val]
# Update counts for the corresponding row and column
row_count[row] += 1
col_count[col] += 1
# Check if the row or column is completely painted
if row_count[row] == n or col_count[col] == m:
return i
return -1 # This should never be reached given the problem constraints
엄청난 센스다. 이런 거 누가 생각해내냐
2.C++
비슷하게 구현했다.(모범 답안이랑)
class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size();
int n = mat[0].size();
unordered_map<int,pair<int,int>> map;
// Map initialize
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
map[mat[i][j]] = {i,j};
}
}
vector<int> row_cnt(m,0);
vector<int> col_cnt(n,0);
for(int k=0;k<arr.size();k++){
int row = map[arr[k]].first;
int col = map[arr[k]].second;
row_cnt[row]++;
col_cnt[col]++;
if(row_cnt[row] == n || col_cnt[col] == m) return k;
}
return -1;
}
};
그나저나 초장의 time limit 걸린 내 Python 코드를 C++로 바꿔도 time limit에 걸리네..
원래 C++은 어지간하면 속도 최적화 되는 거 아니었는감 ㅠㅠ
class Solution {
public:
bool bingo(const vector<vector<bool>>& temp){
int m = temp.size();
int n = temp[0].size();
// row check
for(int i=0;i<m;i++){
if(find(temp[i].begin(),temp[i].end(),false) == temp[i].end()) return true;
}
// col check
for(int j=0;j<n;j++){
vector<bool> arr = {};
for(int i=0;i<m;i++){
arr.push_back(temp[i][j]);
}
if(find(arr.begin(),arr.end(),false) == arr.end()) return true;
}
// No bingo case
return false;
}
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
int m = mat.size();
int n = mat[0].size();
vector<vector<bool>> visited(m,vector(n,false));
for(int k=0;k<arr.size();k++){
bool cond = false;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(mat[i][j]==arr[k]){
visited[i][j] = true;
cond = true;
break;
}
}
if(cond) break;
}
if(bingo(visited)) return k;
}
return -1;
}
};