[Python] 프로그래머스 가장 큰 정사각형 찾기, 백준 2304

1. 문제 - 프로그래머스 가장 큰 정사각형 찾기

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

 

해당 문제는 다이나믹 프로그래밍(DP)로 풀이할 수 있다.

 

1) 행과 열이 각각 최대값이 1000임

--> 행과 열을 반복하며 1을 마주칠때마다 정사각형을 이루는지 판단하려면 반복문이 하나 더 들어가야하는데, 최악의 경우 시간복잡도가 1000^3 = 10^9이 넘어갈 수 있다.

--> 코딩테스트에서는 일반적으로 1억 = 10^8번 연산을 기준으로 판단하므로, 시간초과가 발생한다.

--> 완전탐색으로 풀이할 수 없어서 다른 알고리즘을 생각해야함

 

2) 만들 수 있는 최대 정사각형이므로 예를들어 3x3인 정사각형을 만들 수 있는 위치의 경우 2x2인 정사각형을 포함하므로, 큰 문제를 작은 문제로 쪼개서 해결할 수 있다.

--> DP로 풀이가능

 

✅ 풀이

첫번째 예시를 가지고 규칙을 찾아내면 다음과 같다.

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

 

(2행 2열) = 1

(2행 3열), (2행 4열), (3행 2열), (3행 3열) = 1 + 1 = 2

각 위치마다 값을 갱신하는 규칙을 찾아보면,

왼쪽, 왼쪽 위, 위쪽의 값이 모두 0이 아니면서 (정사각형을 형성하기 위한 조건) 이 중 최솟값 + 1 이라는 규칙이 성립함을 알 수 있다.

따라서 해당식을 코드로 옮기면 다음과 같다.

 

def solution(board):
    n = len(board)
    m = len(board[0])
    
    def can_square(i, j):   # 정사각형을 이루는지 판단하는 함수
        if board[i][j] != 0 and board[i-1][j-1] != 0 and board[i-1][j] != 0 and board[i][j-1] != 0:
            return True
        
        return False
    
    for i in range(1, n):
        for j in range(1, m):
            if can_square(i, j):
                board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
                
    answer = 0   # 정사각형이 아얘 없을 수도 있음
    for i in range(n):
        for j in range(m):
            answer = max(answer, board[i][j])    # 배열 중 최대값 구하기
            
    return answer ** 2    # 정사각형의 넓이이므로 제곱

 

그런데 다른 사람들 풀이를 보니, can_suqare(i, j) 함수가 board[i][j] == 1 이어도 해당 규칙이 성립함을 알 수 있었다.

어차피 대각선이나 왼쪽, 위가 0인 경우에 정사각형의 최소값은 자기 자신인 1일 수 밖에 없으니까 0 + 1 = 1 이 성립한다.

 

따라서 아래와 같이 풀이하는 것도 가능하다.

def solution(board):
    n = len(board)
    m = len(board[0])
    
    for i in range(1, n):
        for j in range(1, m):
            if board[i][j] == 1:
                board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1]) + 1
                
    answer = 0   # 정사각형이 아얘 없을 수도 있음
    for i in range(n):
        for j in range(m):
            answer = max(answer, board[i][j])
            
    return answer ** 2

 

2. 문제 - 백준 2304 창고 다각형

https://www.acmicpc.net/problem/2304

 

구현 문제이다.

 

✅ 풀이

n = int(input())
max_height = 0    # 높이의 최대값 기준으로 왼쪽, 오른쪽 나누기 위함
left = []         # 왼쪽 좌표 리스트
right = []        # 오른쪽 좌표 리스트
arr = []

for _ in range(n):
  l, h = map(int, input().split())
  max_height = max(max_height, h)
  arr.append((l, h))

arr = sorted(arr, key=lambda x:x[0])   # x좌표 기준으로 정렬한 다음 높이가 최대인 직사각형 기준으로 왼쪽, 오른쪽 나누기 위함. 먼저 좌표들을 x 기준으로 정렬

max_height_duo = (0, 0)
for l, h in arr:
  if h == max_height:
    max_height_duo = (l, h)   # 높이가 최대인 (x, y) 쌍 찾기

for l, h in arr:
  if l < max_height_duo[0]:     # 높이가 최대인 직사각형 기준으로 왼쪽, 오른쪽 나눔
    left.append((l, h))
  else:
    right.append((l+1, h))     # x좌표의 오른쪽에서 오른쪽끼리 뺴서 계산하므로 계산의 편의성을 위해 + 1

left.append(max_height_duo)    # 높이가 최대인 직사각형 기준으로 x좌표끼리 계산하여 영역을 더해줘야하므로 추가함
right.insert(0, max_height_duo)    # 높이가 최대인 직사각형의 면적도 계산해주어야하므로 right에 추가

curr = 0
answer = 0
for i in range(1, len(left)):          # 최대 높이 직사각형 기준으로 왼쪽은 (뒤 x좌표 - 앞 x좌표) * 갱신되는 높이의 최대값 공식 성립
  curr = max(curr, left[i-1][1])          # 최대값 갱신
  answer += (left[i][0] - left[i-1][0]) * curr

curr = 0
for i in range(len(right)-1, 0, -1):
  curr = max(curr, right[i][1])        # 최대값 갱신
  answer += (right[i][0] - right[i-1][0]) * curr   # 최대 높이 직사각형 기준으로 오른쪽은 (뒤 x좌표 - 앞 x좌표) * 갱신되는 높이의 최대값 공식
  # 이때 높이의 최대값은 뒤에서부터 갱신해야함

print(answer)

 

해당 문제의 규칙을 찾으면, 높이가 최대인 직사각형을 기준으로

왼쪽은 순서대로 갱신된 높이 최대값 * (뒤 x좌표 - 앞 x좌표)를 모두 더한 값이고

오른쪽은 역순으로 순회했을 때 갱신된 높이 최대값 * (뒤 x좌표 - 앞 x좌표)를 모두 더한 값이다.

 

따라서

1) 높이가 최대인 직사각형의 (x, y) 좌표를 찾아 저장한 다음

2) 해당 기준으로 left, right 배열로 입력된 좌표들을 각각 분리한뒤

3) 왼쪽은 순서대로 순회하면서 (뒤 x좌표 - 앞 x좌표) * 갱신되는 높이의 최대값을 더해나가고

4) 오른쪽은 순서대로 순회하면서 (뒤 x좌표 - 앞 x좌표) * 갱신되는 높이의 최대값을 더해나간다.

 

✅ 다른 사람 풀이

n = int(input())
max_height_idx = 0
max_height = 0
arr = [0] * 1001   # x 범위 1000 이하

for _ in range(n):
  l, h = map(int, input().split())
  arr[l] = h
  if h > max_height:
    max_height = h      # 높이의 최대값 알아내기
    max_height_idx = l   # 높이의 최대값을 가지는 직사각형 좌표 알아내기

answer = 0
curr = 0
for i in range(max_height_idx):   # 왼쪽
  curr = max(arr[i], curr)
  answer += curr

curr = 0
for i in range(1000, max_height_idx, -1):   # 오른쪽
  curr = max(arr[i], curr)
  answer += curr

answer += max_height
print(answer)

 

위와 같이 간결하게 풀이하는것도 가능하다. 따로 left, right 배열을 만들지 않아도

높이의 최대값을 가지는 직사각형이 존재하는 인덱스를 알아낸뒤, 범위값만 지정하면 왼쪽 오른쪽 다르게 계산할 수 있다.