가장 큰 정사각형 찾기 (프로그래머스 Lv 2)

문제 링크

나는 일단 마땅한 풀이가 떠오르지 않아, brute force로 우선 접근했다.

  • max_length = 주어진 2차원 배열에서 만들 수 있는 최대 정사각형의 변의 길이


첫번째 풀이

while max_length > 0:
	for i in range(height - max_length):
		for j in range(width - max_length):
			# 구현
			..

	max_length -= 1

height과 width 값에서 max_length를 뺀 것만큼 반복하고, max_length를 줄여나가는 식으로 반복을 돌렸다.

(해당 좌표에서 max_length 만큼의 정사각형이 성립이 되는지 bool 타입 메서드를 따로 만들어서 사용함)

정확성 모두 통과했지만, 효율성 다 실패


두번째 풀이

거꾸로 접근해서, max_length를 0부터 증가시키는 방법을 사용했다. max_length 만한 정사각형이 만들어지는지 판단하는 메서드는 모든 요소가 1로 구성되어 있는지 확인하는 방식이었는데, 이것도 y축만 돌면서 해당 배열에 0이 있으면 False를 반환하도록 바꿨다.

정확성 테스트에서 속도는 굉장히 빨라졌지만, 효율성 테스트는 여전히 모두 실패


세번째 풀이 (결국 해답 참고)

질문 게시판 통해서 DP로 풀라는 내용을 봤는데, 전혀 떠오르지 않았다. 그래서 결국 해답을 찾아서 봄. 이런 천재적인 생각은 어떻게 하는건지.. 노력해야겠다.. 👊🏻


전체적인 로직

  • board 배열과 같은 크기의 배열 선언(각 좌표를 포함하여 만들 수 있는 가장 큰 정사각형의 한 변의 길이를 원소로 함)
  • 가장자리 위치한 원소들은 1이라면 무조건 1
  • (i, j) 위치의 원소가 0이면 0, 1이면 (i-1, j-1), (i-1, j), (i, j-1) 위치의 값을 보고 결정
  • (i-1, j-1), (i-1, j), (i, j-1) 위치 값들을 보고 각각 정사각형을 그리면, 항상 원소가 1인 영역을 확인할 수 있다. (작은 문제로 쪼개서 생각하는게 그래서 중요한 것 같음)
  • 그 정사각형 영역을 보면, (i, j) 좌표를 포함한 정사각형의 한 변의 길이를 식으로 세울 수 있다.