프로그래머스 [lv2] 가장 큰 정사각형 파이썬

 

이건 못 풀어서 다른 분 풀이를 참고하였다.

# 프로그래머스 우수 풀이 참고

def solution(board):
    ss = {}
    answer = 0
    for y, line in enumerate(board):
        for x, v in enumerate(line):
            if v == 0:
                continue
            ss[(x,y)] = s = min(
                ss.get((x-1,y), 0),
                ss.get((x,y-1), 0),
                ss.get((x-1,y-1), 0)
            ) + 1
            answer = max(answer, s ** 2)
    return answer

 

배운 점

python dictionary의 get()메소드를 배울 수 있었는데,

get()의 첫번째 인자는 key로, 두 번째 인자는 value가 된다.

이 때, key값이 dictionary에 존재하지 않으면, key값의 value값(두 번째 인자)을 매핑해준다.

반대로, key 값이 이미 dictionary에 존재하면 기존의 value값을 return 한다.

a = {'a': 1, 'b': 2}

print(a.get('a', 3))
# 출력: 1

print(a.get('c', 3))
# 출력: 3

 

다른 풀이

def solution(board):
    for row in board:
        if sum(row):
            answer = 1
            break
    else:
        return 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 ** 2
    

 

핵심

answer = max(answer, board[i][j]) 라인을 이해해야한다.

여기서 board[i][j]란 정사각형 하단 우측의 값이며, 정사각형 내부의 원소 값이 모두 0이 아닐 때 +1 이 되는 값이다.

그렇기 때문에 당연히 board[i][j]의 값이 가장 클 것이라고 착각하는 경우가 있다.

이러한 점을 방지하고자 answer 값을 할당할 땐, max() 메서드를 사용하여 board[i][j] 보다 큰 값이 있을 때 update를 해준다.