가장 붐비는 키오스크 직사각형 찾기

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

algorithm medium matrix-prefix-sum 함수명: maxKioskTrafficRectangle 제한 시간: 200ms

격자 안에서 크기가 고정된 직사각형 하나를 골라, 그 안의 합이 가장 크게 되도록 만드는 문제입니다.

문제 설명

정수로 이루어진 2차원 배열 grid, 직사각형의 높이 h, 너비 w가 주어집니다.

grid 안에서 크기가 정확히 h x w인 연속 직사각형 하나를 골랐을 때, 그 안에 포함된 모든 수의 합의 최댓값을 반환하는 maxKioskTrafficRectangle 함수를 작성하세요.

직사각형은 격자 칸 경계에 맞게 선택해야 하며, 회전할 수 없습니다.

예를 들어 3 x 4 격자에서 2 x 2 직사각형을 고른다면 가능한 모든 위치를 살펴본 뒤, 그중 합이 가장 큰 값을 답으로 반환하면 됩니다.

제한사항

1 <= grid.length <= 300
1 <= grid[0].length <= 300
-1000 <= grid[r][c] <= 1000
1 <= h <= grid.length
1 <= w <= grid[0].length
grid의 모든 행 길이는 같습니다.
반환값은 정수입니다.

예시

입력:

grid = [
  [3, 1, 2, 4],
  [0, 6, 1, 2],
  [7, 2, 8, 1]
], h = 2, w = 2

출력: 17

입력:

grid = [
  [-5, -2],
  [-1, -7]
], h = 1, w = 1

출력: -1

힌트

모든 직사각형 안의 칸을 매번 직접 더하면 너무 느릴 수 있습니다.
어떤 위치까지의 누적합을 미리 저장해 두면, 직사각형 합을 네 군데 값만으로 계산할 수 있습니다.
모든 값이 음수일 수도 있으니 초기 답을 0으로 두면 틀릴 수 있습니다.

해설

이 문제의 핵심은 2차원 누적합입니다.

직사각형 후보는 많지만, 각 후보의 합을 매번 직접 더하면 h x w만큼 시간이 들고 전체적으로 비효율적입니다. 대신 prefix[r][c]를 (0, 0)부터 (r - 1, c - 1)까지의 합으로 정의하면, 아무 직사각형의 합도 O(1)에 구할 수 있습니다.

1. 2차원 누적합 만들기

보통 편하게 계산하려고 행과 열을 하나 더 둔 (rows + 1) x (cols + 1) 배열을 만듭니다.

prefix[r][c] =
  grid[r - 1][c - 1]
  + prefix[r - 1][c]
  + prefix[r][c - 1]
  - prefix[r - 1][c - 1];

여기서 마지막에 한 번 빼 주는 이유는, 위쪽 누적합과 왼쪽 누적합을 더할 때 왼쪽 위 영역이 두 번 포함되기 때문입니다.

2. 직사각형 합 구하기

왼쪽 위가 (r1, c1), 오른쪽 아래가 (r2, c2)인 직사각형 합은 아래처럼 계산할 수 있습니다.

sum =
  prefix[r2 + 1][c2 + 1]
  - prefix[r1][c2 + 1]
  - prefix[r2 + 1][c1]
  + prefix[r1][c1];

고정 크기 h x w 직사각형이라면, 각 시작점 (top, left)에 대해 끝점은 (top + h - 1, left + w - 1)로 바로 정해집니다.

3. 모든 시작점을 순회하며 최대값 갱신

가능한 모든 top, left를 돌면서 각 직사각형 합을 계산하고 최댓값을 갱신하면 됩니다.

이 방식의 시간 복잡도는 다음과 같습니다.

누적합 생성: O(rows * cols)
모든 직사각형 검사: O(rows * cols)
전체: O(rows * cols)

즉, 매번 직사각형 내부를 다시 더하는 방식보다 훨씬 효율적입니다.

이 문제를 통해 익혀야 할 감각은, 2차원 구간 합 문제는 누적합으로 직사각형 하나의 합을 즉시 구하도록 바꿀 수 있다는 점입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과