프로그래머스 - 가장 큰 정사각형(Level 2)/Wanna Be 컴잘알

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/12905#

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스

 

- 문제 - 

 

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

- 접근 -

 

1. 이중 포문을 사용해서 경우의 수를 직접 탐색하려고하면 O(N^3)이 되어 최대 ROW길이가 1000이므로 1000^3=1,000,000,000 이므로 약 10초의 시간이 걸린다. 따라서 시간복잡도를 줄이기 위해 DP를 사용해야한다. 문제 해결 방식은 다음과 같다.

 

2. 해당 인덱스의 map 값이 1일 경우 왼쪽, 위쪽, 왼쪽위쪽의 최소값 +1이 현재 길이가된다. 

최대값을 저장해두었다가 넓이를 구할 때 사용하면된다.

 

- 코드 -

 

c++

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;


int map[1000][1000];
int row;
int col;
int dp[1000][1000];

int solution(vector<vector<int>> board)
{
	row = board.size();
	col = board[0].size();

	for (int i = 0; i < row; i++) {
		for (int k = 0; k < col; k++) {
			map[i][k] = board[i][k];
			dp[i][k] = board[i][k];
		}
	}
	int answer = map[0][0];


	for (int i = 1; i < row; i++) {
		for (int k = 1; k < col; k++) {
			if (map[i][k] == 1) {
				dp[i][k] = min({ dp[i - 1][k - 1], dp[i - 1][k] ,dp[i][k - 1] }) + 1;
				if (answer < dp[i][k])
					answer = dp[i][k];
			}
		}
	}

	return answer*answer;
}

 

python3 (추가 업로드)

def solution(board):
    length=0
    flag = False
    map = [rv for rv in board]

    for ri,rv in enumerate(board):
        for ci,cv in enumerate(rv):
            if ri==0 or ci==0 :
                if board[ri][ci]==1:
                    length = max(length,1)
                continue            
            minimum = min(map[ri-1][ci],map[ri][ci-1])
            minimum = min(minimum,map[ri-1][ci-1])

            if board[ri][ci]==1:
                map[ri][ci]= minimum+1
                length = max(length,map[ri][ci])

    answer = length*length

    return answer