[프로그래머스] 가장 큰 정사각형 찾기- Python (효율성이 원인이라면)

프로그래머스 문제 정복기

 

난이도 :  lv2

---

🔗 Link

---

 

https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

📑 Summary

---

 1과 0으로만 존재하는 표가 존재할 때, 해당 표에서 1로만 이루어질 수 있는 정사각형 중 가장 큰 정사각형을 찾아 넓이를 반환하는 문제이다.

 

🔑 How to solve? 

---

필자 역시 처음에 효율성 테스트를 틀렸다. 사실 효율성 테스트에서 어느 정도 틀릴 수 있겠다고 생각했지만, 테스트 케이스 19번까지 파란불이었다가, 효율성 가서 죄다 틀린 것에 허탈함을 느꼈다. 해당 문제는 효율성 테스트 배점이 매우 높다. 테스트 케이스 19개를 맞췄는데도 60점 미만의 점수가 의미하는 것은 이 문제의 핵심은 효율성이라는 의미이다.

 

 

문제를 보고 쉽다는 생각과 함께 가볍게 풀었다면, 이와 비슷한 코드가 나왔을 것이다.

def solution(board):
    height = len(board)
    width = len(board[0])
    for i in range(min(height,width),0,-1):
        for r in range(0,height):
            if r+i-1 < height:
                for c in range(0,width):
                    if  c+i-1< width:
                        toggle = True
                        for row in board[r:r+i]:
                            if 0 in row[c:c+i]:
                                toggle = False
                        if toggle:
                            return i*i
    return 0

중첩 for문을 4개나 사용하였기 때문에, 이것을 일부 수정한다고, 효율성 문제를 해결할 수가 없어보였다. 따라서 코드를 갈아엎었고, dp를 이용하여 해결하였다.

 

 

갑자기 DP ? 🤔

 해당 문제를 DP로 이용한 이유는 간단하다. 우선, 반복문을 줄이기 위해선 연산을 줄여야 한다. 메모이제이션을 이용한다면, 연산의 횟수를 줄일 수 있다. 가장 큰 이유는 반복 가능한 부분이 존재한다는 것이다.

 

반복 가능한 부분이 어디있어?

 위 실패 코드에서 필자는 정사각형을 판단하기 위해, 길이가 2 이상인 사각형들은 오른쪽, 아래쪽, 대각선의 1의 개수를 확인하는 방식으로 문제를 풀었다. (문제에서는 0을 찾아 toggle을 이용해 구현하였지만, 논리는 같다.) 즉, 큰 사각형은 옆 바운더리 또한 정사각형임을 보증한다. 이를 이용하면 쉽게 DP를 이용할 수 있다. 그림을 보자.

 

(구별을 위해 색을 모두 다르게 썼다.) 위 그림은 길이가 2인 정사각형을 판단하는 예제이다. 기준 정사각형을 중심으로 왼쪽, 위, 대각선이 모두 1이라면, 기준점을 포함하여 2인 정사각형이 된다. 그렇다면 길이가 다른 경우는 어떻게 될까? 

 

 

 

길이가 다르더라도, 인접 블록이 모두 정사각형이므로, 보다 큰 정사각형이 만들어질 수 있다. 다만 크기가 다르므로, 가장 작은 정사각형보다 큰 정 사각형이 만들어진다. 이를 통해 해당 문제에서는 인접 블록이 모두 정사각형이라면, 자신을 포함하여 더 큰 정사각형을 만들 수 있다. 단, 인접블록 중 하나라도 0이라면(없다면), 자기 자신의 크기가 가장 큰 사각형이 된다.

 

즉, 미리 인접 블록만 알고 있다면, 재사용이 가능해진다. 계속 인접 블록만 확인하며, 정사각형 블록의 최대 크기를 구할 수 있기 때문이다.

 

Q1. 그런데 실패 케이스에서는 우하향(오른쪽, 아래, 대각선)을 이용하다가 왜 좌상 향으로 인접 블록을 바꿨나요?

 좋은 지적이다. DP를 사용하기 위해서는 인접 행렬에 대해서는 사전에 값을 주어야하기 때문에 배열을 정의할 때 좌측 상단부터 정의하기 하는 특성상 첫 열과 첫 행이 가장 구현에 편하기 때문이다.

 

 

위 내용을 통해 해당 문제에서 사용할 DP를 정의하면 다음과 같다. 기준 블록이 좌표로 구성되어 있으므로 DP변수는 2차원으로 구성된다.

 

DP [][] : 해당 블록을 기준으로 인접 블록 중 가장 작은 값 +1 정사각형

 

코드로 풀어보면 아래와 같다. 

 

 

💡 Code

---

#   Link
#   https://programmers.co.kr/learn/courses/30/lessons/12905

def solution(board):
    answer = 0
    dp=[[0 for _ in range(len(board[0]))] for _ in range(len(board))]
    
    # 첫열과 행을 미리 셋팅하는 부분
    dp[0] = board[0]
    for row in range(len(board)):
        dp[row][0] = board[row][0]


	# 
    for row in range(0,len(dp)):
        for col in range(0,len(dp[0])):
        	# 첫열과 첫행 부분은 넘기며, 현재 블록 값이 1인 경우에만 계산
            if (row - 1 >= 0) and (col -1 >= 0) and board[row][col] ==1:
            	
                dp[row][col] = min(dp[row][col-1],dp[row-1][col],dp[row-1][col-1])+1

    for i in range(len(dp)):
        temp = max(dp[i])
        answer = max(answer, temp)


    # 앞의 행의 가잗큰값만을 뽑아오므로 이렇게하면안됨
    # answer = max(max(max(dp)),answer)
    return answer*answer

 

 

Comment 📜

---

 비슷한 문제를 풀었던 기억이 있어서 쉽게 수정했다. 화이트보드를 주고 설명하라면, 쉽게 할 수 있겠는데, 포스팅으로 쓰는 게 어려워 시간을 더 잡아먹었다..😂 오히려 포스팅 때문에 다른 블로거님들의 포스팅을 보았고.. 참으로 대단하다 싶었다. 아직도 남에게 설명하는 부분이 부족한 것 같다. 좀 더 잘 표현할 수 있도록 노력해야겠다.

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.