혼자서 해결할 수 있을 때까지 LeetCode 솔루션 공부 8일차: 문제#221.최대 제곱(중/자바스크립트)

소개: 저는 전직 회계사에서 2022년 1월 코딩 부트캠프를 졸업한 소프트웨어 엔지니어입니다. 알고리즘과 데이터 구조는 현재 대부분의 기술 회사에서 인터뷰에서 피할 수 없는 부분입니다. 그리고 내 친구 중 한 명이 최고의 기술 회사에 들어가려면 60초 미만의 중간 leetcode 문제를 해결해야 한다고 말했습니다. 그래서 나는 구직 중에 그것을 하는 방법을 배우기 시작해야겠다고 생각했습니다.

나는 어떤 문제(심지어 쉬운 문제라도)를 해결하는 방법에 대한 단서가 없기 때문에 시간을 낭비하고 알아낼 수 없다고 생각했습니다. 내 접근 방식은 다음과 같습니다.

무작위로 leetcode 문제를 선택하거나 대상 회사의 온라인 평가를 선택하십시오.

Youtube 또는 LeetCode 토론 섹션에서 1-2 솔루션을 연구하십시오. 하나의 무차별 대입 솔루션, 다른 하나가 더 최적입니다.

자세한 설명과 함께 블로그 게시물을 작성하고 솔루션을 더 잘 이해하는 데 도움이 되도록 구두 연습을 합니다.

솔루션을 보지 않고 LeetCode에서 솔루션을 코딩합니다.

망각 곡선 퇴치: 앞으로 3일 동안 질문을 다시 하십시오. 그리고 정기적으로 돌아와서 문제를 재검토하십시오.

문제 #221. 최대 제곱

Difficulty: Medium Language: JavaScript
0과 1로 채워진 m x n 이진 행렬이 주어지면 1만 포함하는 가장 큰 정사각형을 찾아 면적을 반환합니다.

예 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],
["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

예 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

예 3:

Input: matrix = [["0"]]
Output: 0

제약:

m == matrix.length

n == matrix[i].length

1 <= m, n <= 300

matrix[i][j]는 '0' 또는 '1'입니다.

해결책:

유투브 영상은 마지막에 링크된 솔루션을 설명하니 말로만 하는 것보다 이해가 더 잘 됩니다.) 이 문제를 해결하는 열쇠는 "1"을 포함하는 최대 길이를 찾아 "0"이 발견되어 루프를 끊을 때까지 새 행렬에 저장하는 것입니다. LeetCode 토론 게시판의 "carti"에서 아래 예를 인용합니다.

이것은 매우 간단하지만 "Cache"(주어진 행렬의 복사본)를 topleft, left, top + 1의 최소값으로 설정하여 무슨 일이 일어나는지 설명하겠습니다.

우리에게 다음이 주어졌다고 가정해 봅시다.

1 1 1
1 1 1
1 1 1

첫 번째 행은 algo에 따라 동일하게 유지되고 우리는 (1,0)에 있습니다. 이것은 첫 번째 열에 있기 때문에 동일하게 유지됩니다.
(1,1)에 도달하면 왼쪽 상단, 왼쪽 상단 및 상단 + 1의 최소값을 취하여 2이므로 Cache는 이제

1 1 1
1 2 1
1 1 1

그리고 우리는 새로운 최대값을 2로 설정했습니다.

더 많은 값을 업데이트하면 캐시는 다음과 같이 됩니다.

1 1 1
1 2 2
1 2 1

그런 다음 마지막 셀 (2,2)에 도달하면 다시 min을 취하면 다음과 같이 됩니다.

1 1 1
1 2 2
1 2 3

새로운 최대값은 3입니다.

결과는 3^2, 즉 9가 되며, 이는 이 예의 답입니다.

솔루션 코드:

function maximalSquare(matrix) {

    if(!matrix || !matrix[0]) return 0

//To deal with edge cases where an empty matrix is given. If
// 'matrix' is false/doesn't exist (note 1) return 0.

    let cache = [...matrix],

//create a copy (note 2) of given array 'matrix'

        height = matrix.length,
        width = matrix[0].length,

//define height and width of the array. Height of the array is
//the length of the array (note 3). And width of the array is the
//length of the first element of the array (note 3 & 4). For
//example, matrix array shown below has width and length of 2.
//Because the length of the matrix array is 2 (there are two
//arrays nested in the matrix array). The length of the first
//array ["0","1"] is also 2, which makes up the width of the
//matrix array.
//       [["0","1"],
//        ["1","0"]]

        solution = Math.max(...matrix[0])

//solution = length of the largest square.
//set the initial value of the solution as the maximum (note 6)
//value of first array element. This is for the edge case where
//there is only one element in the matrix array. And because our
//iteration below starts from index 1 (the second element) of both
//row and column; if there is only one array in the matrix, the
//solution would be the max value of array. For example, if we
//have a matrix of [["0","1"]], the largest square that contains 1
//will be 1*1=1.

     for (let i = 0; i < matrix.length; i++) {
         solution = Math.max(solution, matrix[i][0])
     }

//This is for the edge case where there are two elements in the
//matrix array and each element is a single element array. For
//example, [["0"],["1"]]. Because our iteration below starts from
//index 1 (the second element) of both row and column; if both
//elements are single element array, the solution would be the max
//value between two elements. For example, if we have a matrix of
//[["0"],["1"]], the max of array[0] is 0 and the max of array[1]
//is one, that will give us the max between two arrays of 1. 

     for (let row = 1; row < height; row++) {

         for (let col = 1; col < width; col++) {


//start interating from second elment of second array (note 7)

             if(matrix[row][col] === "1") {
                 cache[row][col] = Math.min(cache[row-1][col],
                     cache[row][col-1],cache[row-1][col-1])+1;

//if "1" if found, then compare it with it's surrounding element
//and save minimum (note 5) of these elements plus 1 and save it
//in the new maxtrix "Cashe" (see explaination above for reason
//behind this step.

               solution = Math.max(cache[row][col], solution);

//update max solution

             }
         }
     }
    return solution **2

//the area of a square is the product of the length of each side
//with itself (note 8)

}

2022년 2월 19일 현재 솔루션 제출 세부정보
(아래 데이터는 매일 새로운 테스트/제출이 있으므로 다를 수 있음)

런타임: 118ms

메모리 사용량: 46.4mb

참조:
LeetCode Problem Link

LeetCode Discussion: carti
Note 1: Logical NOT(!)
Note 2: Spread syntax(...)
Note 3: Array.length
Note 4: Access an array item by its index
Note 5: Math.min()
Note 6: Math.max()
Note 7: for loop
Note 8: Exponentiation(**)
Blog Cover Image Credit