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

https://programmers.co.kr/learn/courses/30/lessons/12905

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

 

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

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

 

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

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