가장 큰 활성 직사각형 구역

자바스크립트 코딩테스트 문제로 histogram-stack 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard histogram-stack 함수명: solution 제한 시간: 600ms

0과 1로 이루어진 격자 grid가 주어질 때, 모든 칸이 1인 축에 평행한 직사각형 중 넓이가 가장 큰 값을 반환하는 solution 함수를 작성하세요.

제한사항

1 <= grid.length <= 200
1 <= grid[i].length <= 200
모든 행의 길이는 같습니다.
grid[i][j]는 0 또는 1입니다.
반환값은 만들 수 있는 가장 큰 직사각형의 넓이입니다.

예시

입력:
```
[
  [1, 0, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [0, 1, 1, 1, 0]
]
```
출력: 6
- 가운데 2행 3열 크기의 직사각형을 만들 수 있습니다.

입력:

[
  [1, 0, 1, 0],
  [1, 0, 1, 1],
  [1, 1, 1, 1],
  [0, 1, 1, 1]
]

출력: 6

오른쪽 아래 쪽에서 넓이 6인 직사각형이 최대입니다.

힌트

각 행을 바닥으로 본다고 생각하면, 위로 연속된 1의 개수를 높이로 가지는 히스토그램을 만들 수 있습니다.
문제는 각 행마다 히스토그램에서 가장 큰 직사각형을 구하는 문제로 바뀝니다.
히스토그램 최대 직사각형은 단조 증가 스택으로 O(m)에 처리할 수 있습니다.

해설

핵심 아이디어는 2차원 문제를 여러 번의 1차원 문제로 바꾸는 것입니다.

위에서부터 행을 한 줄씩 내려오면서, 각 열에 대해 현재 행까지 연속된 1의 높이를 계산합니다.
- 현재 칸이 1이면 높이를 1 증가시킵니다.
- 현재 칸이 0이면 그 열의 높이는 0으로 리셋됩니다.
이렇게 만든 높이 배열은 “현재 행을 바닥으로 하는 히스토그램”이 됩니다.
이제 각 행마다 히스토그램에서 만들 수 있는 최대 직사각형 넓이를 구합니다.
- 높이가 증가하는 인덱스를 스택에 쌓습니다.
- 더 낮은 막대를 만나면, 스택에서 막대를 꺼내며 그 막대가 최소 높이인 직사각형 넓이를 계산합니다.
- 끝까지 남은 막대를 한 번에 처리하려고 마지막에 높이 0인 가상의 막대를 하나 덧붙여 flush하면 편합니다.
모든 행에서 구한 최대 넓이 중 가장 큰 값을 답으로 반환합니다.

왜 이 방식이 맞을까요?

어떤 직사각형이든 “맨 아래 행”이 있습니다.
그 아래 행을 처리하는 순간, 그 직사각형의 각 열 높이는 최소한 직사각형의 높이만큼 쌓여 있습니다.
따라서 그 직사각형은 해당 행의 히스토그램 최대 직사각형 계산 과정에서 반드시 후보로 고려됩니다.

시간 복잡도는 행 수를 n, 열 수를 m이라 할 때 O(n * m)입니다. 각 행마다 높이 갱신 O(m), 히스토그램 최대 직사각형 계산 O(m)만 필요합니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.