JS Coding Blog

겹쳐 붙인 홍보 보드의 전체 넓이

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

today hard geometry-sweep 함수명: unionAreaOfPromoBoards 제한 시간: 400ms

직사각형 홍보 보드 여러 장이 겹쳐 붙어 있을 때, 중복 없이 실제로 덮인 전체 넓이를 구하는 문제입니다.

문제 설명

축에 평행한 직사각형 목록 rectangles가 주어집니다.

각 직사각형은 [x1, y1, x2, y2] 형태이며,

  • 왼쪽 아래 꼭짓점이 (x1, y1)
  • 오른쪽 위 꼭짓점이 (x2, y2) 를 뜻합니다.

여러 직사각형이 서로 겹칠 수 있고, 일부는 완전히 다른 직사각형 안에 들어 있을 수도 있습니다.

이때 적어도 하나의 직사각형에 덮이는 영역의 총 넓이를 반환하는 unionAreaOfPromoBoards 함수를 작성하세요.

단, 변이나 꼭짓점만 맞닿는 것은 넓이 겹침으로 보지 않습니다.

제한사항

  • 1 <= rectangles.length <= 50000
  • rectangles[i] = [x1, y1, x2, y2]
  • -1000000 <= x1 < x2 <= 1000000
  • -1000000 <= y1 < y2 <= 1000000
  • 반환값은 JavaScript의 Number로 안전하게 표현되는 범위 안에 들어옵니다.
  • 가능한 한 O(n log n) 수준으로 해결해 보세요.

예시

  • 입력: rectangles = [[-1, 0, 2, 3], [1, 1, 4, 4]] → 출력: 16
  • 입력: rectangles = [[0, 0, 2, 2], [2, 0, 5, 2], [1, 2, 4, 4]] → 출력: 16
  • 입력: rectangles = [[1, 1, 5, 5], [2, 2, 3, 3], [0, 0, 6, 2]] → 출력: 24

첫 번째 예시에서

  • 첫 보드 넓이: 9
  • 둘째 보드 넓이: 9
  • 겹치는 부분 넓이: 1

겹치는 부분은 [1, 2) × [1, 3)이라 넓이가 2이고, 따라서 전체 넓이는 9 + 9 - 2 = 16입니다.

두 번째 예시에서는 첫째와 둘째 보드는 x = 2 선에서만 맞닿으므로 겹친 넓이는 0입니다.

힌트

  • 모든 보드 쌍의 겹침을 직접 계산하면 너무 느립니다.
  • x축 방향으로 왼쪽 변과 오른쪽 변을 이벤트처럼 훑어 보세요.
  • 어떤 x 구간에서 현재 덮인 y 길이만 알 수 있다면, 그 구간의 넓이는 가로 길이 × 덮인 세로 길이로 바로 계산할 수 있습니다.
  • 문제는 겹친 y 구간을 중복 없이 합치는 것이므로, 좌표 압축과 세그먼트 트리를 함께 쓰는 전형적인 sweep line 패턴을 떠올릴 수 있습니다.

해설

직사각형 합집합 넓이를 단순히 처리하면 겹침이 복잡하게 얽혀 O(n^2) 이상으로 커지기 쉽습니다.

이 문제의 핵심은 세로 띠(strip) 단위로 넓이를 쌓는다는 것입니다.

1. x축 이벤트로 바꾸기

직사각형 [x1, y1, x2, y2]는 x축 기준으로 보면 두 순간만 중요합니다.

  • x1에서 이 직사각형이 활성화됨
  • x2에서 이 직사각형이 비활성화됨

즉 각 직사각형을 다음 두 이벤트로 바꿀 수 있습니다.

  • (x1, +1, y1, y2)
  • (x2, -1, y1, y2)

이 이벤트들을 x 오름차순으로 정렬해 왼쪽에서 오른쪽으로 훑습니다.

2. 현재 x띠에서 필요한 정보

어떤 두 인접한 이벤트 x = prevX와 x = currX 사이에서는 활성화된 직사각형 집합이 변하지 않습니다.

따라서 이 구간의 넓이는

(currX - prevX) * 현재 덮인 전체 y 길이

입니다.

결국 매 순간 필요한 것은 현재 활성 직사각형들이 y축에서 덮고 있는 총 길이입니다.

3. 왜 단순 누적이 안 될까?

예를 들어 현재 활성 직사각형들의 y구간이

  • [1, 5)
  • [2, 4)
  • [3, 7)

이라면 길이를 그냥 더하면 4 + 2 + 4 = 10이지만, 실제로 덮인 구간은 [1, 7) 하나이므로 길이는 6입니다.

즉 겹친 y구간은 중복 없이 합쳐진 길이를 알아야 합니다.

4. 좌표 압축 + 세그먼트 트리

직사각형의 y좌표는 최대 1000000 범위라서 그대로 배열을 만들 수 없습니다. 대신 등장하는 모든 y1, y2만 모아 정렬한 뒤 좌표 압축을 합니다.

그러면 세그먼트 트리의 각 노드는 압축된 y구간 하나를 나타낼 수 있습니다.

각 노드에는 보통 두 정보를 둡니다.

  • coverCount: 이 구간을 완전히 덮는 활성 직사각형 개수
  • coveredLength: 현재 실제로 덮인 길이

갱신 규칙은 다음과 같습니다.

  • coverCount > 0 이면 이 노드 구간 전체가 덮입니다.
  • coverCount == 0 이면 자식들의 coveredLength 합으로 결정합니다.
  • 리프 노드라면 실제 길이는 ys[right + 1] - ys[left]처럼 압축 전 좌표 차이로 계산합니다.

이 구조를 쓰면 어떤 직사각형이 시작하거나 끝날 때마다 [y1, y2) 구간에 +1 또는 -1을 반영할 수 있고, 루트 노드의 coveredLength가 곧 현재 전체 덮인 y 길이가 됩니다.

5. sweep 순서

  1. 모든 직사각형을 x 이벤트 2개로 변환합니다.
  2. 모든 y좌표를 모아 정렬 후 압축합니다.
  3. 이벤트를 x 오름차순으로 순회합니다.
  4. 새 이벤트를 처리하기 전에, 직전 x와 현재 x 사이 넓이를 누적합니다.
  5. 현재 이벤트의 [y1, y2)를 세그먼트 트리에 반영합니다.
  6. 루트의 덮인 y 길이를 다음 띠 계산에 사용합니다.

6. 변만 닿는 경우가 왜 자동 처리될까?

우리는 직사각형을 [x1, x2) × [y1, y2)처럼 생각해도 넓이는 같고, 이 방식에서는

  • x2에서 끝나는 보드와
  • 같은 x2에서 시작하는 다른 보드 가 있어도 폭이 0인 선에서만 만난 것이므로 넓이가 중복 계산되지 않습니다.

y축도 마찬가지라서 변만 맞닿는 경우는 겹침 면적 0으로 자연스럽게 처리됩니다.

7. 복잡도

  • 이벤트 수는 2n
  • 이벤트 정렬: O(n log n)
  • 각 이벤트당 세그먼트 트리 갱신: O(log n)

따라서 전체 시간 복잡도는 O(n log n)이고, 추가 공간 복잡도도 O(n) 수준입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

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

댓글

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