LeetCode [1380]: Lucky Numbers in a Matrix

📌 LeetCode [1380]: Lucky Numbers in a Matrix

🔗 문제 링크

---

문제 설명 📄

주어진 행렬에서 Lucky Number를 찾아야 합니다. Lucky Number는 다음 조건을 만족하는 숫자입니다:

1. 해당 행의 최소값.
2. 해당 열의 최대값.

모든 Lucky Number를 리스트로 반환하세요.

---

문제 접근 방식 📋

1. 각 행의 최소값을 구합니다.
2. 각 열의 최대값을 구합니다.
3. 행의 최소값과 열의 최대값의 교집합을 찾으면 Lucky Number가 됩니다.

---

Solution 💻

첫 번째 코드

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        minCol = [float('inf') for _ in range(len(matrix))]
        maxRow = [0 for _ in range(len(matrix[0]))]

        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                minCol[row] = min(minCol[row], matrix[row][col])
                maxRow[col] = max(maxRow[col], matrix[row][col])

        answer = []
        pattern = {}
        minCol += maxRow

        for i in minCol:
            if i not in pattern:
                pattern[i] = 0
            else:
                answer.append(i)

        return answer

시간 복잡도 ⏲️

• 행 최소값 및 열 최대값 계산: (O(m \cdot n)), (m)은 행 개수, (n)은 열 개수.
• 중복 검사 및 결과 계산: (O(m + n)).

공간 복잡도 🗄️

• 최소값과 최대값 저장 (O(m + n)).
• 중복 검사 패턴 저장 (O(m + n)).

---

리팩토링 🛠️

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        minCol = {min(row) for row in matrix}
        maxRow = {max(col) for col in zip(*matrix)}
        return list(minCol & maxRow)

시간 복잡도 ⏲️

• 행 최소값 및 열 최대값 계산: (O(m \cdot n)).
• 집합 교집합 계산: (O(\min(m, n))).

공간 복잡도 🗄️

• 최소값 및 최대값 저장: (O(m + n)).

---