2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 7월 20일 (토)
Leetcode daily problem
1380. Lucky Numbers in a Matrix
https://leetcode.com/problems/lucky-numbers-in-a-matrix/?envType=daily-question&envId=2024-07-19
Problem
고유한 숫자로 구성된 m x n 행렬이 주어지면 행렬의 모든 "lucky numbers" 를 순서에 관계없이 반환합니다.
"lucky numbers"는 행의 최소 요소이고 열의 최대 요소인 행렬의 요소이다.
Solution
Greedy
행렬에서 lucky numbers는 그 행에서 가장 작고 그 열에서 가장 큰 숫자이다. 이를 찾기 위해서
(1) 각 행에서 가장 작은 값을 찾는다. 이 값은 rMin 이다 .
그리고 이 rMin에서 가장 큰 값을 찾는다 이 값은 rMinMax 이다.
(2) 각 열에서 가장 큰 값을 찾는다. 이 값은 cMax이다.
그리고 이 cMax 중에서 가장 작은 값을 찾는데 이 값은 cMaxMin이다.
(3) rMinMax와 cMaxin이 같으면 이 값이 lucky numbers이다. 그렇지 않으면 럭키넘버는 없는 것이다.
Code
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
n, m = len(matrix), len(matrix[0])
r_min_max = float('-inf')
for i in range(n):
r_min = min(matrix[i])
r_min_max = max(r_min_max, r_min)
c_max_min = float('inf')
for i in range(m):
c_max = max(matrix[j][i] for j in range(n))
c_max_min = min(c_max_min, c_max)
if r_min_max == c_max_min:
return [r_min_max]
else:
return []Complexicity
시간 복잡도
첫 번째 루프에서 각 행에서 최소 값는 찾는 연산을 하기 위해 n번 반복되고, 각 반복에서 'min(matrix[i])' 의 m개의 요소 중 최소 값을 찾는 연산으로 O(nm)이 소요 된다.
두 번째 루프에서 각 열에 대한 최대 값을 찾는 연산을 수행하면서 m번 반복되고, n개의 요소 중 최대 값을 찾는 연산으로 o(mn)이 소요된다.
즉 전체 시간 복잡도는 O(n*m)이다.
공간 복잡도
추가적으로 사용되는 데이터 구조가 없어 공간 복잡도는 O(1) 이다.
- 추가로 한줄로 파이써닉하게 끝낸 코드발견
class Solution:
def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
return set(map(min,matrix)) & set(map(max,zip(*matrix)))
해당 코드에서 'map(min, matrix) 또한 각 행에서 최소값을 찾고, 행렬이 nm 크기 일 때 각 행에 대한 최소 값을 찾는 작업 O(m)이 필요로해 o(nm) 연산이다.
또한 'zip(matrix)' 는 행렬을 전치하는 작업으로, 행렬의 모든 요소를 한 번씩 접근해 o(nm)이 소요된다.
전치된 행렬의 각 열에서 최대값을 찾는 작업인'map(max, zip(matrix)' 또한 전치된 행렬이 각 열의 원래 행렬의 행과 동일한 크기이고, 각 열에 대한 최대 값을 찾는 작업 또한 O(nm) 이다.
두 집합의 교집합을 찾는 작업은 두 집합의 크기가 n, m 이라고 할 때 O(min(n,m)) 이다.
즉, 전체 시간복잡도는 O(n*m) 이 소요되고,
공간복잡도에서 행렬의 전치는 새로운 리스트를 생성하지 않고, 각 열의 튜플을 반환하는 방식이므로 추가 공간이 필요 없다.
그러나 'set(map(min, matrix)', 'set(map(max, zip(*matrix)))' 에서 각 집합은 최대 n개의 요소와 m개의 요소를 가질 수 있고, 두 집합을 저장하는데 공간이 필요하므로 전체 공간 복잡도는 O(n+m) 이다.
