가장 큰 정사각형 찾기

프로그래머스

 

처음에는 각 칸에 대해 length를 1부터 1씩 증가시키면서 정사각형이 안 되는 경우에는 다음 칸으로 넘어가도록 구현했는데, 바로 효율성 검사에서 시간 초과가 나부렸다.

뭔가 사각형 여부를 구할 때마다 계속 같은 연산을 하는 느낌이 들긴 했는데, 이걸 어떻게 개선해야 할 지 모르겠어서 다른 사람의 풀이를 참고했다.

 

---

풀이 코드

def solution(board):
    n = len(board)
    m = len(board[0])
    
    dp = [[0] * (m+1) for _ in range(n+1)]
    
    # dp 테이블에 board 테이블을 한칸씩 오른쪽, 아래로 이동시켜서 저장
    for i in range(n):
        for j in range(m):
            dp[i+1][j+1] = board[i][j]
    
    # 정사각형의 한 변의 최대 길이
    max_length = 0
    
    # dp[i][j] = 1인 경우, 왼쪽, 왼쪽위, 위 dp 테이블 값 중 작은 것에 1을 더한다.
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if dp[i][j] == 1:
                dp[i][j] = min(dp[i-1][j] , dp[i][j-1], dp[i-1][j-1]) + 1
                max_length = max(max_length, dp[i][j])
                
                
    return max_length * max_length

 

 

DP로 푸는 건 상상도 못했다.

오랜만에 DP 문제를 보니 어지러워서 현기증이 날 지경이다.

그래도 지금 데여봤으니 앞으로는 이런 문제를 만나면 풀 수 있을 듯하다!

 

 

---

참고 링크

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

 

[프로그래머스] 가장 큰 정사각형 찾기 Java 풀이