[프로그래머스 Lv2] 가장 큰 정사각형 찾기 (DP)

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

문제 설명

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

예를 들어

1 2 3 4

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

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

1 2 3 4

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합니다.

 

---

 

[내 풀이]

※ 소요시간 : 32 분, 실패

※ 풀이 전략

-  가장 큰 정사각형을 찾는 법: 일단 n이 10^3 이므로, 10*n^2 정도의 알고리즘 이 필요 : 스택 아니면 DP겠다 싶었다. 
-  for 문으로 전체 i, j를 돌고 나면 연산이 완료되어 있어야 한다.
- 그럼 이전 값을 이용할 수 있게 설계 할 수 있다는 뜻 
- 결과적으로 a[i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1]) + 1알아낼 수 있었고, 그래서 DP로 풀었다. 

# 32분
def solution(board):
    a = [[0]*(c:= len(board[0])) for _ in range(r:= len(board))]

	# a[i][j] 초깃값 설정
    for j in range(c):
        a[0][j] = board[0][j]
    for i in range(r):
        a[i][0] = board[i][0]

    # for문으로 a[i][j] 값 구하기
    for i in range(1, r):
        for j in range(1, c):
            if board[i][j] == 1:
                a[i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1]) + 1
        
    maxL = 0 #초깃값
    for i in range(r):
        maxL = max(maxL, max(board[i]))
    
    return maxL**2

Traceback (most recent call last):
  File "/solution_test.py", line 6, in <module>
    from solution import *
  File "/solution.py", line 12
    a = [[0]*(c:= len(board[0])) for _ in range(r:= len(board))]
                                               ^
SyntaxError: assignment expression cannot be used in a comprehension iterable expression

 

 

※ 중요 포인트

SyntaxError: assignment expression cannot be used in a comprehension iterable expression

- 직역하면 assignment expression (:= )는 comprehension(리스트 컴프리헨션) iterable expression (range(r:len(baord)) 부분에 사용될 수 없다. 라고 뜬다. 사실 :=을 쓰지 않고 한 줄 더 쓰면 되는 부분이지만, 왜 안되는지 검색을 해봤다. 

https://peps.python.org/pep-0572/#scope-of-the-target

링크: https://peps.python.org/pep-0572/#scope-of-the-target

PEP 572 – Assignment Expressions | peps.python.org

- 검색해 본 결과, 파이썬 자체에서 '기호 테이블 분석기'가 가장 왼쪽의 반복 가능 표현식(range(2)), 와 (k:=stuff) 부분 사이에서 이름이 재사용되는 시기를 쉽게 감지할 수 없어 버그가 생길 소지가 있어서 원천적으로 막아놨다는 뜻인 듯 하다. 사람의 생각으로는 당연히 구분 가능할 것이라고 생각하는데, 파이썬 자체에서 막아놨다고 하니 결국은 못 쓰는 듯 하다. 

 

 

---

[내 풀이2]

※ 소요시간 : 5 분, 성공

※ 수정한 부분 

-  r = len(board) 로 := 연산자를 쓰지 않게 수정

- maxL을 구하는 구문에서 a 행렬이 아니라 board 행렬을 넣어버린 문제 수정 

def solution(board):
    r = len(board) # 
    a = [[0]*(c:= len(board[0])) for _ in range(r)]

	# a[i][j] 의 초깃값 설정
    for j in range(c):
        a[0][j] = board[0][j]
    for i in range(r):
        a[i][0] = board[i][0]

    # for문으로 a[i][j] 값 구하기
    for i in range(1, r):
        for j in range(1, c):
            if board[i][j] == 1:
                a[i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1]) + 1
    
    maxL = 0 # 초깃값 0
    for i in range(r):
        maxL = max(maxL, max(a[i]))
    
    return maxL**2

 

※ 중요 포인트

- 자꾸 대상 값을 이상한 것을 입력하는 실수를 한다... a[i]를 넣어야 하는데, board[i]를 넣어버리다니 ㅠㅠ 

---

[다른 사람의 풀이]

※ 풀이 전략

- 풀이 순서는 정말 똑같다. 

def solution(board):
    n = len(board)
    m = len(board[0])

    # dp 준비
    dp = [[0]*m for _ in range(n)]
    dp[0] = board[0]
    for i in range(1,n):
        dp[i][0] = board[i][0]
    
    # 2중 포문으로 연산
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    
    # 최대 넓이 구하기
    answer = 0
    for i in range(n):
        temp = max(dp[i])
        answer = max(answer, temp)
    
    return answer**2

 

※ 중요 포인트

- dp 테이블을 나는 a 테이블로 지정했는데, 이 분 처럼 명확하게 dp로 이름 짓는 게 좋겠다 싶다.