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

문제

https://programmers.co.kr/learn/courses/30/lessons/12905?language=python3

풀이

우선 처음에 잘못 접근했던 코드부터 기록해볼까 한다.

def solution(board):
    cube = [0] * len(board[0])
    for row in board :
        cube = [c+r for c,r in zip(cube, row)]
    
    max_val = max(cube)
    while max_val > 0 :
        max_len = 0
        start = cube.index(max_val)
        for i in range(start, len(cube)):
            if cube[i] >= max_val : max_len += 1
            if max_len == max_val : return max_val**2
            if cube[i] < max_val : max_len = 0
        
        max_val -= 1
        
    return 0            

행 단위로 훑으면서 각 열별로 덧셈을 진행한다.

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0
---------------
2   3   4   3

덧셈이 완료된 상태에서, 가장 큰 값을 비교 값으로 잡아
한 행씩 비교하면서 비교 값보다 크거나 같은 값을 카운트 한다.
그러다 비교 값과 같은 길이가 나오면 그 비교값의 제곱을 정답으로 반환한다.

2   3   4   3
---------------
4 -> 1
3 -> 3
return 3^2

접근은 그럴듯 했으나, 결과는 처참했다.

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.1MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	실패 (0.02ms, 10.3MB)
테스트 7 〉	실패 (런타임 에러)
테스트 8 〉	통과 (0.02ms, 10.3MB)
테스트 9 〉	실패 (런타임 에러)
테스트 10 〉	실패 (런타임 에러)
테스트 11 〉	실패 (런타임 에러)
테스트 12 〉	실패 (런타임 에러)
테스트 13 〉	실패 (0.02ms, 10.2MB)
테스트 14 〉	실패 (런타임 에러)
테스트 15 〉	실패 (런타임 에러)
테스트 16 〉	실패 (0.03ms, 10.2MB)
테스트 17 〉	실패 (런타임 에러)
테스트 18 〉	실패 (런타임 에러)
테스트 19 〉	실패 (런타임 에러)

심지어 이리저리 뒤틀어봐도 시간초과까지 뜨는 상황이었다.
도저히 방법이 떠오르지 않아서 결국 검색의 힘을 빌렸다.
아래는 CodeDrive블로그를 참고한 결과다.

def solution(board):
    zero_check = 0
    for row in board :
        zero_check += sum(row)
    if zero_check == 0 : return 0
    
    max_val = 1
    for i in range(1, len(board)) :
        for j in range(1, len(board[0])) :
            if board[i][j] == 0 : continue
                
            board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
            if board[i][j] > max_val :
                max_val = board[i][j]
    
    return max_val ** 2

1. 첫 번째 반복문에서 모든 행을 탐색하면서 1이 없는지 확인한다.
2. 두 번째 반복문부터 (1,1) 블럭을 기준으로 탐색을 시작하는데, 좌, 좌상, 상단을 확인하기 떄문이다.
3. 만약 (i, j)가 0이라면 사각형이 아니므로 탐색할 필요가 없다.
4. 만약 (i, j)가 1이라면, 좌, 좌상, 상단을 확인해서 최소값+1을 대입시킨다.

코드 설명은 이정도로 된거같고, 어떤 현상이 일어나나 직접 확인해보자.

#1
0	1	1	1
1	*1	1	1    좌상에서 최소값 0 발견, +1 대입
1	1	1	1
0	0	1	0

#2
0	1	1	1
1	1	*1	1    최소값 1 발견, +1 대입
1	1	1	1
0	0	1	0

#3
0	1	1	1
1	1	2	*1    최소값 1 발견, +1 대입
1	1	1	1
0	0	1	0

#4
0	1	1	1
1	1	2	2    최소값 1 발견, +1 대입
1	*1	1	1
0	0	1	0

#5
0	1	1	1
1	1	2	2    최소값 1 발견, +1 대입
1	2	*1	1
0	0	1	0

#6
0	1	1	1
1	1	2	2    최소값 2 발견, +1 대입
1	2	2	*1
0	0	1	0

#7
0	1	1	1
1	1	2	2    최소값 2 발견, +1 대입
1	2	2	3
0	0	*1	0

Dynamic Programming을 통한 해결 방법이었는데,
분명 학부과정에서 접한 경험이 있는 풀이 방식이다.
2차원 배열 문제를 마주했을 때 떠올릴 수 있도록 기억파편을 꼭 남겨두자.