URL https://programmers.co.kr/learn/courses/30/lessons/12905
문제 설명
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
예를 들어
1
2
3
4
5
1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
- 가 있다면 가장 큰 정사각형은
1
2
3
4
5
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의 2 x 2를 계속 탐색하면서 가장 마지막 board의 (1,1)에 최소값 +1을 해줌
- 위의 내용을 반복하면 아래 처럼된다.
1
2
1 1 -> 1 1
1 1 1 2
1
2
3
4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 -> 1 2 1 -> 1 2 2 -> 1 2 2 -> 1 2 2 -> 1 2 2
1 1 1 1 1 1 1 1 1 1 2 1 1 2 2 1 2 3
결국 answer는 마지막 board의 (1,1)이 가장 큰 값을 곱해주면 됨
- 하지만 아래의 케이스는 answer가 1일 경우인데 0을 리턴하게 된다
1 2
1 0 -> 1 0 0 0 0 0
- 따라서 answer가 1인 경우 (1 * 1) = 1을 따로 만들어 주어야 하며
그냥 board를 for문돌면서 행의 sum이 1이상이면 일단 answer = 1로, 아니면 0으로 하였다.
- 참고 URL https://velog.io/@djagmlrhks3/Algorithm-Programmers-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95-%EC%B0%BE%EA%B8%B0-by-Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(board):
for row in board:
if sum(row):
answer = 1
break
else:
answer = 0
for i in range(1, len(board)): #행
for j in range(1, len(board[0])): #열
if board[i-1][j-1] and board[i-1][j] and board[i][j-1] and board[i][j]:
board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
answer = max(answer, board[i][j])
return answer * answer
1
2
board = [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]
solution(board)
1
9
1
2
board = [[0,0,1,1],[1,1,1,1]]
solution(board)
1
4
1
2
board = [[1, 0], [0, 0]]
solution(board)
1
1