[프로그래머스] 가장 큰 정사각형 찾기 [연습문제] [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의 최댓값의 제곱을 반환해주면 해결 할 수 있다.

반응형

+ Recent posts