[PCCP] Lv2: 가장 큰 정사각형 찾기(12905) 해설

문제

- 문제 링크: 가장 큰 정사각형 찾기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: board의 행의 길이

- M: board의 열의 길이

- 중첩 반복문은 총 N*M번 수행하므로 최종 시간 복잡도: O(N*M)

class Solution {
    public int solution(int[][] board) {
        // 주어진 2차원 보드의 행과 열의 개수를 변수에 저장
        int row = board.length;
        int col = board[0].length;
        
        // 각 행과 열을 순회하며 최적의 정사각형을 찾기
        for (int i = 1; i < row; ++i) {
            for (int j = 1; j < col; ++j) {
                // 현재 위치의 값이 1인 경우를 확인
                if (board[i][j] == 1) {
                    // 현재 위치에서 위, 왼쪽, 대각선 왼쪽 위의 값들을 가져옴
                    int up = board[i - 1][j];
                    int left = board[i][j - 1];
                    int upLeft = board[i - 1][j - 1];
                    // 현재 위치의 값을 이전 위치들의 값들 중 가장 작은 값에 1을 더한 값으로 업데이트
                    board[i][j] += Math.min(up, Math.min(upLeft, left));
                }
            }
        }
        
        int answer = 0;
        // 보드에서 가장 큰 값(최대 정사각형의 한 변의 길이)을 찾기
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                answer = Math.max(answer, board[i][j]);
            }
        }
        // 최대 정사각형의 넓이를 반환
        return answer * answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: board의 행의 길이

- M: board의 열의 길이

- len을 구하는 함수는 시간 복잡도: O(1)

- 중첩 반복문은 총 N*M번 수행

- 최종 시간 복잡도: O(N*M)

def solution(board):
    # 주어진 2차원 보드의 행과 열의 개수를 변수에 저장
    ROW, COL = len(board), len(board[0])
    
    # 각 행과 열을 순회하며 최적의 정사각형을 찾기
    for i in range(1, ROW):
        for j in range(1, COL):
            # 현재 위치의 값이 1인 경우를 확인
            if board[i][j] == 1:
                # 현재 위치에서 위, 왼쪽, 대각선 왼쪽 위의 값을 가져옴
                up, left, up_left = (board[i - 1][j], board[i][j - 1], board[i - 1][j - 1])
                
                # 현재 위치의 값을 이전 위치들의 값들 중 가장 작은 값에 1을 더한 값으로 업데이트
                board[i][j] = min(up, left, up_left) + 1
                
    # 보드에서 가장 큰 값(최대 정사각형의 한 변의 길이)를 찾음
    max_val = max(max(row) for row in board)
    
    # 최대 정사각형의 넓이 반환
    return max_val**2

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: board의 행의 길이

- M: board의 열의 길이

- 길이를 구하는 것의 시간복잡도는 O(1)이고 중첩 반복문은 총 N*M번 수행하므로 최종 시간복잡도: O(N * M)

function solution(board) {
    // 주어진 2차원 보드의 행과 열의 개수를 변수에 저장
    const ROW = board.length;
    const COL = board[0].length;
    
    // 각 행과 열을 순회하며 최적의 정사각형ㅇ르 찾음
    for (let i = 1; i < ROW; ++i) {
        for (let j = 1; j < COL; ++j) {
            // 현재 위치의 값이 1인 경우를 확인
            if (board[i][j] === 1) {
                // 현재 위치에서 위, 왼쪽, 대각선 왼쪽 위의 값들을 가져옴
                const up = board[i - 1][j];
                const left = board[i][j - 1];
                const upLeft = board[i - 1][j - 1];
                
                // 현재 위치의 값을 이전 위치들의 값들 중 가장 작은 값에 1을 더한 값으로 업데이트
                board[i][j] = Math.min(up, left, upLeft) + 1;
            }
        }
    }
    
    // 보드에서 가장 큰 값(최대 정사각형의 한 변의 길이)을 찾음
    const maxVal = Math.max(...board.map((row) => Math.max(...row)));
    
    // 최대 정사각형의 넓이를 반환
    return maxVal * maxVal;
}

solution 2)

import

solution 3)

import