[프로그래머스] 가장 큰 정사각형 찾기 [연습문제] [python] Level2
문제 설명
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
예를 들어
가 있다면 가장 큰 정사각형은
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.
설계 및 구현
접근 방법
먼저 입출력 예시1에서 가장 큰 정사각형을 찾는 과정을 살펴보면
먼저 이런식으로 리스트의 위쪽과 왼쪽으로 0으로 이루어진 데이터를 한줄씩 늘린다.
그후 밑줄 쳐진 0부터 시작한다. 0의 인덱스를 board[i][j]라고 할때
board[i][j] >0 이면 board[i-1][j], board[i][j-1], board[i-1][j-1] 중 최솟값+1로 갱신해준다.
이 과정을 끝까지 하면
board는 이렇게 변하게 된다 리스트안의 하얀색 사각형이 가장 큰 정사각형이 된다. 3은 가장 큰 정사각형의 한 변의 길이가 된다.
고로 max(board)의 제곱을 리턴해주면 해결 할 수 있는 문제이다.
my_solution
def solution(board):
# 1
res = []
bigboard = []
leng1 = len(board) + 1
leng2 = len(board[0]) + 1
# 2
for i in range(leng1):
bigboard.append([])
for j in range(leng2):
if i == 0 or j == 0:
bigboard[i].append(0)
else :
bigboard[i].append(board[i-1][j-1])
# 3
for i in range(leng1-1):
for j in range(leng2-1):
a = min(bigboard[i+1][j],bigboard[i][j],bigboard[i][j+1])
if bigboard[i+1][j+1] > 0:
bigboard[i+1][j+1] = a+1
res.append(bigboard[i+1][j+1])
# 4
return max(res)**2
1. board를 확장시켜 저장할 bigboard선언 bigboard의 가로 세로 길이 선언 및 초기화
2. bigboard에 데이터를 저장한다.
3. bigboard[i+j] >0 이면 min(bigboard[i+1][j],bigboard[i][j],bigboard[i][j+1]) + 1을 저장하면서
나중에 max()를 사용해 최댓값을 찾기위해 res에 계속 값을 저장해준다.
bignoard리스트를 모두 순회한다.
4. max(res) **2 => res의 최댓값의 제곱을 반환해주면 해결 할 수 있다.
'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 카펫 [완전탐색] [python] (1) | 2020.09.24 |
---|---|
[프로그래머스] 위장 [해시] [python] (0) | 2020.09.24 |
[프로그래머스] 구명 보트 [탐욕법(Greedy)] [python] (0) | 2020.09.23 |
[프로그래머스] H-index [정렬] [python] (0) | 2020.09.23 |
[프로그래머스] 전화번호 목록 [해시] [python] (0) | 2020.09.23 |