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

문제 설명

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

예를 들어

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

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

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

입출력 예 설명

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

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

무지성 풀이

• 그냥 되겠지 싶어서 풀었더니 됐네?
  • for문으로 그려가면서 테스트케이스 상상하던거 다 넣고 요리조리 해서 풀었다.
  • 눈에 보이는 문제는 쉽구나... ㅡ.ㅡ;

• 효율성 테스트까지 있었네?
  • 500ms면 가까스로 된 듯...
  • 효율성 테스트 더 빠르게 하려면 역시 다른 방식을 써야겠지?

def solution(board):
    answer = board[0][0]
    for y in range(1, len(board)):
        for x in range(1, len(board[0])):
            if board[y][x] != 0:
                min_value = min(board[y][x-1], board[y-1][x], board[y-1][x-1])
                board[y][x] = min_value + 1
                answer = max(answer, min_value + 1)
    return answer ** 2
    
정확성  테스트
테스트 1 〉	통과 (0.00ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (0.06ms, 10MB)
테스트 4 〉	통과 (0.08ms, 10.1MB)
테스트 5 〉	통과 (0.08ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.01ms, 10.1MB)
테스트 8 〉	통과 (0.01ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.07ms, 10.2MB)
테스트 11 〉	통과 (0.02ms, 10.2MB)
테스트 12 〉	통과 (0.03ms, 10.2MB)
테스트 13 〉	통과 (0.02ms, 10.3MB)
테스트 14 〉	통과 (0.03ms, 10.2MB)
테스트 15 〉	통과 (0.05ms, 10.3MB)
테스트 16 〉	통과 (0.05ms, 9.99MB)
테스트 17 〉	통과 (0.09ms, 10MB)
테스트 18 〉	통과 (1.08ms, 10.1MB)
테스트 19 〉	통과 (1.00ms, 10.1MB)

효율성  테스트
테스트 1 〉	통과 (499.56ms, 31.2MB)
테스트 2 〉	통과 (474.39ms, 30.7MB)
테스트 3 〉	통과 (512.72ms, 30.7MB)

고수의 풀이

• 약간 더 빠른 방식.
  • 변수에 할당하고 +1하는 연산까지 제거해버린...
  • +1을 할 필요가 없구나, 어차피 그 배열 안에 1이 들어있으니까 더해버리면 되는거네...
  • 그리고 answer에 max...하는건 마지막으로 빼서 그것만 돌리면 더 빠름

def solution(board):
    answer = 0
    for i in range(1, len(board)) :
        for j in range(1, len(board[0])) :
            if board[i][j] >= 1 :
                board[i][j] += min(board[i-1][j-1],board[i][j-1],board[i-1][j])

    for i in board :
        if answer < max(i) : answer = max(i)
    return answer * answer
    
정확성  테스트
테스트 1 〉	통과 (0.00ms, 10MB)
테스트 2 〉	통과 (0.04ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10MB)
테스트 4 〉	통과 (0.04ms, 10.1MB)
테스트 5 〉	통과 (0.08ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.02ms, 10.1MB)
테스트 8 〉	통과 (0.02ms, 10.2MB)
테스트 9 〉	통과 (0.03ms, 10.1MB)
테스트 10 〉	통과 (0.04ms, 10MB)
테스트 11 〉	통과 (0.03ms, 10.1MB)
테스트 12 〉	통과 (0.02ms, 10.1MB)
테스트 13 〉	통과 (0.02ms, 10.2MB)
테스트 14 〉	통과 (0.06ms, 10MB)
테스트 15 〉	통과 (0.07ms, 10.2MB)
테스트 16 〉	통과 (0.07ms, 9.81MB)
테스트 17 〉	통과 (0.04ms, 10.1MB)
테스트 18 〉	통과 (0.88ms, 10.1MB)
테스트 19 〉	통과 (0.90ms, 10.1MB)

효율성  테스트
테스트 1 〉	통과 (410.92ms, 31.1MB)
테스트 2 〉	통과 (423.89ms, 30.5MB)
테스트 3 〉	통과 (425.65ms, 30.8MB)

• 그럼 한줄 체크 끝났을 때 max()로 비교하면 되는거 아니냐?

def solution(board):
    answer = board[0][0]
    for y in range(1, len(board)):
        for x in range(1, len(board[0])):
            if board[y][x] != 0:
                board[y][x] += min(board[y][x-1], board[y-1][x], board[y-1][x-1])
        answer = max(answer, max(board[y]))
    return answer ** 2
    
정확성  테스트
테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (0.04ms, 10.4MB)
테스트 5 〉	통과 (0.04ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10MB)
테스트 8 〉	통과 (0.01ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.04ms, 10.2MB)
테스트 11 〉	통과 (0.03ms, 10.2MB)
테스트 12 〉	통과 (0.02ms, 10.3MB)
테스트 13 〉	통과 (0.02ms, 10.3MB)
테스트 14 〉	통과 (0.03ms, 10.3MB)
테스트 15 〉	통과 (0.04ms, 10.2MB)
테스트 16 〉	통과 (0.04ms, 10.3MB)
테스트 17 〉	통과 (0.05ms, 10.3MB)
테스트 18 〉	통과 (1.01ms, 10.3MB)
테스트 19 〉	통과 (1.03ms, 10MB)

효율성  테스트
테스트 1 〉	통과 (397.91ms, 31MB)
테스트 2 〉	통과 (412.73ms, 30.5MB)
테스트 3 〉	통과 (412.15ms, 30.9MB)