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

가장 큰 정사각형 찾기

문제 설명

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

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

1	2	3	4
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으로만 이루어져 있습니다.

입출력 예

board	answer
[ [0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0] ]	9
[ [0,0,1,1],[1,1,1,1] ]	4

입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

입출력 예 #2

| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |

로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

해결한 코드

function solution(board){
	var answer = 0
    var x = board[0].length
    var y = board.length
    var max = 0
    if(x <= 1 || y <= 1) return 1
    
    for(var i=1; i<x; i++){
    	for(var j=1; j<y; j++){
        	if(board[i][j] >= 1){
            	var up = board[i-1][j]
                var left = board[i][j-1]
                var upperLeft = board[i-1][j-1]
                var min = Math.min(up, left, upperLeft)
                board[i][j] = min+1
                max = Math.max(max, min+1)
            }
        }
    }
    answer = Math.pow(max, 2)
    return answer
}

알고리즘

1. board 배열의 x, y축의 길이를 구한다.
2. board의 (1,1)부터 돌면서 board[i][j]가 1이 이상인 경우에 상단, 왼쪽, 왼쪽상단의 값을 구한다.
   ex. 다음의 경우

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

   빨간 1의 상단, 왼쪽, 왼쪽상단 값은 (1, 0, 1)이 된다.
3. 상단, 왼쪽, 왼쪽상단 값의 최솟값에 +1을 해준다.
   ex. (1, 0, 1)의 최솟값은 0 + 1 = 1
4. 최솟값 + 1을 board[i][j]에 넣는다.

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

5. max = 0 과 최솟값 + 1 을 비교해 더 큰 값을 max에 넣는다.
   현재 max = 1
6. 다음으로, (1,2)의 상단, 왼쪽, 왼쪽상단 값은 (1, 1, 1) -> 최솟값 + 1 -> 1 + 1 = 2

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

7. max = 1 과 최솟값 +1 을 비교해 더 큰 값을 max에 넣는다.
   현재 max = 2
8. 위 과정을 반복하면

   0	1	1	1
   1	1	2	2
   1	2	2	3
   0	1	2	3

   max = 3
9. max를 제곱하여 answer에 넣는다.
   3*3 = 9
10. answer를 반환한다.
11. 하지만 만약 board가

    0	1	0

    혹은

    0
    1
    0

이런식으로 오게 되면 가장 큰 정사각형은 1이 된다. 이 경우에는 1을 반환해주도록 한다.

결국 좋은 방법을 찾지 못해 검색했다. 어릴때 사고력 수학같은 과목으로 공부했던 방법과 같은..
코테를 공부할수록 사고력 수학을 공부하는 느낌이 든다. 새로운 풀이나 좋은 방법을 찾아가는 과정에서 자책보다는 기쁨과 즐거움을 느끼면서 공부하자 !