프로그래머스. 가장 큰 정사각형 찾기

tose33 2021. 11. 16. 14:18

코딩테스트 연습 - 가장 큰 정사각형 찾기

[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9

programmers.co.kr

처음에 (0,0)부터 끝까지 다 순회하면서 확인해볼까 생각했지만 이 경우 O(n^3)이 되고

n의 최댓값이 1000으로 시간이 너무 길어진다.

(0,0) 부터 순회하면서 계산하는데 [i][j]값이 0인 경우는 제외한다. (0이면 정사각형을 만들수 없으므로)

왼쪽, 왼쪽위, 위의 값중 가장 작은값 + 1 이 현재 위치의 정사각형의 변의 길이이다.