[Week 6-1] 🔥특강 1일차

6주차 화요일

• 개인 공부

---

오랜만에 알고리즘 문제 풀기~

[LeetCode 1380. Lucky Numbers in a Matrix]

원소의 중복이 없는 m x n 행렬이 주어질 때 행렬에 존재하는 모든 Lucky number 를 반환하기
Lucky number : 자신이 속한 행에서는 최소값이며 자신이 속한 열에서는 최대값이 되는 원소

• 접근
  각 행에서 최소값을 찾아서 최소값이 속한 열의 최대값과 비교하기
  시간 복잡도 : O(m*n) = O(n^2)

• 코드

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        # lucky number : 자신이 속한 행에서는 최소, 열에서는 최대가 되는 수
        M = len(matrix[0])
        N = len(matrix)
        luckies = []
        
        for row in matrix:
            minNum = min(row)
            minIdx = row.index(minNum)
            
            col = [matrix[i][minIdx] for i in range(N)]
            if max(col) == minNum:
                luckies.append(minNum)
                
        return luckies
                

• 더 빠른 방법은 없을까?
  충격
  엄청나게 파이썬스러운 코드를 발견했다. zip이나 unpacking을 어떻게 쓰는지 머리로는 알고 있는데 문제에 적용할 생각을 못 했다... 행에서의 최소값과 열에서의 최대값을 각각 찾아서 교집합을 구한다는 발상도 못 했다. 잊지 말고 꼭 써먹어야지.
  시간 복잡도 : O(N)? zip의 시간 복잡도를 잘 모르겠다.
  파이썬 3부터는 zip이 iterator 객체 형태로 동작하기 때문에 zip의 시간 복잡도가 O(N)이라고 한다. 파이썬 2에서는 zip이 list를 반환하기 때문에 시간 복잡도가 O(N*M)이다.

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        # lucky number : 자신이 속한 행에서는 최소, 열에서는 최대가 되는 수
        
        matrix_T = list(zip(*matrix))
        rowMin = []
        colMax = []
        
        for row in matrix: # 각 행에서의 최소값
            rowMin.append(min(row))
            
        for col in matrix_T: # 각 열에서의 최대값
            colMax.append(max(col))
                          
                          
        return set(rowMin) & set(colMax)