Lv.2dpgrid
가장 넓은 정사각형 잔디밭
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
공원 관리소가 공원 부지를 격자로 나눈 지도 grid를 가지고 있습니다. grid[i]는 i번째 줄을 나타내는 문자열이고,
각 글자는 잔디가 자란 칸이면 '1', 흙이나 돌이 드러난 칸이면 '0'입니다.
돗자리 축제를 위해 잔디 칸으로만 이루어진 정사각형 구역 중 가장 넓은 곳을 찾으려 합니다. 정사각형의 변은 격자선과 나란해야 합니다.
가능한 가장 큰 정사각형의 **넓이(칸 수)**를 반환하세요. 잔디 칸이 하나도 없으면 0입니다.
입출력 예
| grid | result |
|---|---|
["10100", "10111", "11111", "10010"] | 4 |
["01", "10"] | 1 |
["0"] | 0 |
입출력 예 설명
예 1 — 1행 2열부터 2행 3열까지(0부터 셈)의 구역이 모두 잔디입니다. 잔디 구역은 없습니다.
예 2 — 잔디 칸이 대각선으로만 놓여 있어 이 최대입니다.
예 3 — 잔디 칸이 없습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(grid: string[]) → int
제한 사항
-
grid.length -
grid[i].length, 모든 줄의 길이는 같습니다. grid[i]는'0'과'1'로만 이루어져 있습니다.
기대 복잡도
- 시간
- O(HW)
- 공간
- O(W)
입출력 예
| grid | 기대 출력 |
|---|---|
["10100","10111","11111","10010"] | 4 |
["01","10"] | 1 |
["0"] | 0 |
힌트
힌트
칸마다 정사각형을 한 줄씩 키워 보며 확인하면, 잔디가 빽빽한 지도에서는 칸 하나에만 이 들어 효율성 테스트를 통과할 수 없습니다.
side[i][j] = "칸 (i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 잔디 정사각형의 변 길이"로 두세요.
(i, j)가 잔디라면
입니다. 세 이웃 중 가장 작은 정사각형이 확장을 가로막기 때문입니다. 흙 칸은 0입니다.
표를 한 번 채우면 이고, 답은 가장 큰 side의 제곱입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |