Posts 가장 큰 정사각형 [Python]
Post
Cancel

가장 큰 정사각형 [Python]

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

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
This post is licensed under CC BY 4.0 by the author.

폰켓몬 [Python]

뉴스 클러스터링 [Python]

Comments powered by Disqus.