[Programmers Lv2, Java] 가장 큰 정사각형

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

 

가 있다면 가장 큰 정사각형 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

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

---

오랜만에 효율성체크가 있는 문제였다.

 

가장 먼저 접근한 방법은 row랑 col이 연속되는 횟수를 적은 2차원 배열을 각각 만들어서,

x, y 지점의 연속된 row값, 연속된 col값이 지금까지 찾은 최대사이즈보다 크면 사이즈 만큼 움직이면서 정사각형이 맞는지 검증하는 방법... 이었는데

효율성3번을 뚫지못했다.

 

그래서 그냥 2중첩 for문 한번에 싹 끝내게 만들어버리자 하고 이런 코드를 짜봤다.

 

 

반복 한 번에 최대한 많은 동작을 시키려니까 굉장히 난잡해졌는데,

대충 row에서 연속된 횟수를 측정하고, 이전 col에서 이 row 값에 연속되고 있는지 테스트하는 값이 있으면 (xTest)

내가 이전 col에서 시작한 test보다 연속값이 크거나 같으면 테스트를 이어서 진행,

연속값이 작지만, 현재 발견된 최대 사이즈보다 크면 테스트사이즈를 줄여서 이어서 진행하는 방식이다.

그러다가 테스트값만큼 연속된 횟수가 진행되면 bigSize를 갱신하고..

만약 x가 0인곳에 도착하면 이전 테스트값을 모두 무효로 만들고..

 

뭐 그런건데, 이 코드에는 엄청난 문제점이 있다.

바로 테스트케이스는 통과를 하는데,

y를 지금처럼 0~board.length로 가는건 괜찮은데 board.length~0으로 진행하면 TC-18이 실패한다.

어딘가에 하자가 있다는 뜻인데...

오늘은 밤이 늦었으니 일단 자고 나중에 생각나면 고쳐봐야겠다.

 

간단하게 고치는 방법으로는 x마다 테스트 List를 만들어서 한 x에 테스트를 2개 이상 돌리게 만들면 모든 케이스를 통과하지만, 효율성을 넘기지 못한다.

ArrayList란...