반응형
def solution(board):
answer = 0
for i in range(len(board)):
for j in range(len(board[0])):
if (i > 0) and (j > 0) and (board[i][j] != 0):
board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1])+1
answer = max(answer, board[i][j])
return answer ** 2
처음엔 이 방법을 생각하기 어려워서 한참 고민하다가 서치를 통해 다른 사람의 풀이를 보고 해결한 것이다.
풀이를 보고도 이해가 잘 안되어서 직접 손으로 그려보기도 했다.
일단 먼저 생각해야 할 것이 정사각형이 되기 위한 조건이다.
왼쪽 윗대각선 , 왼쪽, 위 이렇게 세방향을 검사해주고 거기서 min+1값을 구하는 것이다.
왜 min값이어야 하는 가? min값으로 해야지 그 위치에서 만들 수 있는 최대 정사각형을 구할 수 있다.
그려보면 더 감이 올 것이다.
말로 표현하기는 어렵지만 그려보는 것이 이해에 제일 도움이 되는 것 같다. 화이팅

반응형
'알고리즘 > 프로그래머스 level 1,2' 카테고리의 다른 글
[파이썬🐍] 프로그래머스 : 방문 길이 (1) | 2021.05.23 |
---|---|
[파이썬🐍] 프로그래머스 : 숫자의 표현 (0) | 2021.05.22 |
[파이썬🐍] 프로그래머스 : 로또의 최고 순위와 최저 순위 (0) | 2021.05.20 |
[파이썬🐍] 프로그래머스 : 땅따먹기 (0) | 2021.05.19 |
[파이썬🐍] 프로그래머스 : 구명보트 (0) | 2021.05.18 |
댓글