프로그래머스 - 가장 큰 정사각형 찾기 (레벨2, swift)

문제출처

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

 

문제설명 

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

 

 

문제풀이

처음에 찾아보지 않고 혼자 해결한 방법대로는 효율성 테스트를 통과하지 못해 결국 검색해 보았다. 효율성을 충족시켜주기 위해서는 동적프로그래밍(Dynamic Programing)을 사용해야 한다고 한다.

 

예를 들어서 살펴보자.

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

(1, 1)을 기준으로 좌측 상단, 상단, 좌측에 있는 값들 중 가장 작은 수를 (1, 1)에 더해준다. 이 경우에는 0이 가장 작은 수이므로 (1, 1)에는 그대로 1이 저장되게 된다. 

 

0	1	1	1
1	1	2	1
1	1	1	1
0	0	1	0

(1, 2)를 기준으로 파란색으로 표시된 숫자들 중 가장 작은 수를 (1, 2)에 더해준다. 1이 가장 작은 수이므로 2가 저장된다.

위 과정을 반복하면 아래와 같은 결과 값이 나오게 된다. 

 

0	1	1	1
1	1	2	2
1	2	2	3
0	0	1	0

여기서 가장 큰 수인 3을 제곱한 9를 반환하면 된다.

(0, 1)에서 부터 3이 있는 (2, 2)의 위치까지 가장 작은 수를 더해주며 반복해줬기 때문에 만약 중간에 0이 있었다면 (2, 2)는 3이라는 숫자가 나올 수 없게 된다. (2, 2)에 3이라는 숫자가 있다는 말은 (0, 1) 에서부터 (2, 2)까지 모두 1로 채워져 있어 3X3의 정사각형이 만들어질 수 있다는 뜻이 된다. 이런 방법을 이용하면 한 번 탐색했던 값을 다시 탐색해 줄 필요가 없기 때문에 매우 효율적이다.

 

단, 위 방법은 행이나 열이 하나인 경우는 계산이 되지 않기 때문에 이러한 경우는 따로 처리해 주어야 한다.

0

1

0

0

 

0

1

0

0