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

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

예를 들어

가 있다면 가장 큰 정사각형은

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2

로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

---

나의 풀이

첫 번째 시도

def solution(board):
    width, height = len(board[0]), len(board)
    startX, startY = 0, 0
    size = min(len(board), len(board[0]))
    
    while size:
        for w in range(startX, width - size + 1):
            for h in range(startY, height - size + 1):
                if isSquare(board, w, h, size):
                    return size**2
        size -= 1
    return 0

def isSquare(board, startW, startH, size):
    for w in range(startW, startW+size):
        for h in range(startH, startH+size):
            if board[h][w] == 0: return False
            
    return True

 

첫 번째 시도 결과

아이디어

1. 주어진 표에서 가장 큰 정사각형의 크기가 될 수 있는 size를 구한다.
2. 1. 가로,  세로 중 더 짧은 것이 가장 큰 정사각형의 size가 될 수 있는 가능성이 있다.
3. 왼쪽 위부터 표를 순회하며 정사각형이 되는 경우가 있는지 확인
   1. 정사각형이 된다면 바로 정사각형의 크기를 return
   2. 정사각형인지 확인하는 isSquare 함수는 주어진 범위에서 0이 발견되면 False, 모두 1이면 True를 반환한다.
4. 정사각형이 되는 경우가 없다면 size를 하나 줄여 2번부터 반복
   1. size가 0이 되면 1이 없는 경우이므로 0을 return

 

정확도는 모두 맞았으나 효율성 테스트에서 통과하지 못했다.

 

두 번째 시도

def solution(board):
    # 첫 번째 시도와 동일

def isSquare(board, startW, startH, size):
    for h in range(startH, startH+size):
        if 0 in board[h][startW: startW+size]: return False
    return True

두 번째 시도 결과

두 번째 시도에는 isSquare() 함수의 동작을 변경하였다.

기존에 이중 반복문으로 모든 요소를 순회하며 검사했는데 이 경우 board가 대부분 1로 채워져있다면 시간이 오래걸린다.

리스트를 모두 순회하는 것보다 in 내장함수를 사용하는 것이 훨씬 빠르기 때문에 각 열을 순회하며 해당 열에 0이 존재하는지 in 으로 확인하는 방법으로 변경했다.

 

다행히 첫 번째 시도와 비교해 상당히 시간이 단축됐다. 하지만 아쉽게도 효율성 테스트는 통과하지 못했다.

세 번째 시도 (성공)

문제가 잘 안풀려 새로운 접근법으로 시도하려 했지만 쉽지 않았기에 힌트를 얻고자 구글링을 했다.

DP(동적 프로그래밍)를 사용하면 된다고 한다.

방법은 다음과 같다.

 

1. (1, 1)부터 검사한다.

   1. 0	1
      1	1

      색칠된 칸이 얼마나 큰 사각형에 포함될 수 있는지 숫자를 나타낸다. 방법은 다음과 같다
   2. 만약 색칠된 칸이 (i, j)라고 했을 때 board[i][j]가 0이면 continue로 넘어간다
   3. 그렇지 않으면 board[i-1][j-1](왼쪽 위 대각선), board[i-1][j](위), board[i][j-1](좌) 중 가장 작은 값 + 1을 board[i][j]에 저장한다.
2. 모든 칸에 대해 검사한다.
3. board에서 가장 큰 값이 가장 큰 정사각형의 한 변 길이가 된다.
4. 가장 큰 값을 제곱하면 답이다.
5. 만약 주어진 board가 한 칸 짜리인 경우 그 값을 return하고 끝낸다.

def solution(board):
    width, height = len(board[0]), len(board)
    if width * height == 1:
        return 1 if width else 0
    size = 0
    for h in range(1, height):
        for w in range(1, width):
            if board[h][w] == 0: continue
            result = min(board[h-1][w-1], min(board[h][w-1], board[h-1][w])) + 1
            if result > size: size = result
            board[h][w] = result
    return size ** 2

테스트 결과