[2024] day 134. Leetcode 2373. Largest Local Values in a Matrix

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 12일 (일)
Leetcode daily problem

786. K-th Smallest Prime Fraction

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/?envType=daily-question&envId=2024-05-11

Problem

n x n 정수 행렬 그리드가 제공될ㄷ 때, (n - 2) x (n - 2) 크기의 정수 행렬 maxLocal을 생성한다.

maxLocal[i][j]는 i + 1행과 j + 1열을 중심으로 한 그리드의 3 x 3 행렬의 가장 큰 값이다. 즉, 그리드에서 인접한 모든 3 x 3 행렬에서 가장 큰 값을 찾고, 생성된 행렬을 반환한다.

Solution

Brute Force

입력 행렬 그리드를 순회하면서 각 원소를 중심으로 (n-2) * (n-2)부분 행렬을 만들어서 그 부분 행렬에서의 최댓값을 찾는 모든 조합을 시도해서 답을 찾는 방식이다.

주어진 행렬에서 특정 위치 (x,y)를 시작점으로 하는 3x3 부분 행렬 내에서 가장 큰 값을 서치한다.

Code

class Solution:

    def find_max(self, grid, x, y):
        max_element = 0
        for i in range(x, x + 3):
            for j in range(y, y + 3):
                max_element = max(max_element, grid[i][j])
        
        return max_element

    def largestLocal(self, grid):
        N = len(grid)
        
        max_local = [[0] * (N - 2) for _ in range(N - 2)]
        for i in range(N - 2):
            for j in range(N - 2):
                max_local[i][j] = self.find_max(grid, i, j)
        
        return max_local

Complexicity

시간 복잡도

이중 반복 루프를 통해 주어진 행렬을 순회하고, 각 원소를 중심으로 부분해 행렬에서의 최댓값을 찾는다. 최댓값을 찾는 것은 상수 시간이 걸리지만 이중 반복문으로 인해서 전체 시간 복잡도는 O(N^2) 이다.

공간 복잡도

주어진 행렬의 부분 행렬의 최댓값을 저장하기 위해 새로운 배열을 생성하므로, 전체 공간 복잡도는 (N-2)*(N-2) 로, O(N^2)이다.