문제 보기 · Level 5 · 연습문제 · 정답률 1% · 푼 사람 151명 (2026-09-30 기준)1
문제
변이 축에 평행한 직사각형 N개가 (x1, y1, x2, y2)로 주어진다. (x1, y1)이 왼쪽 아래, (x2, y2)가 오른쪽 위이고, 서로 겹칠 수 있다. 직사각형들이 덮는 전체 넓이를 돌려준다.
- 1 ≤ N ≤ 100,000
- 0 ≤ x1 < x2 ≤ \(10^9\), 0 ≤ y1 < y2 ≤ \(10^9\), 정수
풀이
막히면 한 단계씩 펼친다.
필요한 개념
세그먼트 트리와 스위핑: 세로선을 왼쪽에서 오른쪽으로 쓸면서, 직사각형이 들어오고 나갈 때마다 “지금 세로로 덮인 길이”를 세그먼트 트리로 고친다. 사건 사이에서는 덮인 길이 × 폭을 더한다.
1단계 · 작은 예로 손으로 풀기
문제의 첫 예시 (0, 1, 4, 4)와 (3, 1, 5, 3)이다. 넓이는 12와 4이고 겹친 곳이 2라 12 + 4 − 2 = 14다.
세로선을 왼쪽에서 쓸며 보면 이렇다.
| x 구간 | 세로로 덮인 y | 덮인 길이 | 더할 넓이 |
|---|---|---|---|
| 0 ~ 3 | 1 ~ 4 | 3 | 3 × 3 = 9 |
| 3 ~ 4 | 1 ~ 4 (1 ~ 3이 겹친다) | 3 | 3 × 1 = 3 |
| 4 ~ 5 | 1 ~ 3 | 2 | 2 × 1 = 2 |
합은 14다. 직사각형이 들어오거나 나가는 x에서만 덮인 길이가 바뀐다.
2단계 · 가장 단순한 방법과 그 속도
x 좌표와 y 좌표를 압축해 칸으로 나누고, 칸마다 어느 직사각형에 덮였는지 본다. 좌표가 각각 20만 개면 칸이 400억 개다. 칸마다 직사각형을 다 보면 더 느리다. 겹친 넓이를 빼고 더하는 포함-배제 원리도 겹침을 봐야 할 직사각형 묶음이 \(2^N - 1\)가지라 어림없다.
3단계 · 핵심 아이디어
- 스위핑: 직사각형마다 왼쪽 변 x1에 “들어옴”, 오른쪽 변 x2에 “나감” 사건을 만들고 x 순서로 정렬한다. 사건 사이에서는 세로로 덮인 길이가 그대로라, (덮인 길이) × (다음 사건까지의 폭)을 더하면 된다. 넓이는 덮인 길이 L(x)를 x로 적분한 값이다. L(x)는 사건 사이에서 일정한 계단 함수라, 이 (길이 × 폭)의 합은 어림값이 아니라 적분과 딱 맞는 리만 합이다.
- y 좌표 압축: 좌표가 \(10^9\)까지라 그대로 배열을 만들 수 없다. 나오는 y 값을 정렬해 번호를 매기면, 이웃한 두 값 사이가 칸 하나다. 좌표가 k개면 칸은 k − 1개이고, 칸마다 실제 길이가 다르다.
- 덮인 길이 트리: 칸 위에 세그먼트 트리를 둔다. 마디마다 “이 마디를 통째로 덮는 직사각형 수”(cnt)와 “이 마디 안에서 덮인 길이”(cov)를 든다. cnt > 0이면 cov는 마디 길이 전체, 아니면 두 자식 cov의 합(잎이면 0)이다. 들어옴은 cnt에 +1, 나감은 −1을 붙이고 위로 cov를 다시 계산한다. 뿌리의 cov가 지금 덮인 길이다.
- 내려보내기가 없다: 나가는 직사각형은 들어올 때와 같은 칸 범위를 쓰므로, +1을 붙인 마디에 그대로 −1이 붙는다. 그래서 cnt를 자식에게 내려보내지 않아도 뿌리의 cov가 늘 맞다.
4단계 · 코드 흐름
- y 값을 모아 정렬하고 값 → 번호 사전을 만든다. 칸 i의 길이는 ys[i + 1] − ys[i]다.
- 칸 수 이상인 2의 거듭제곱 size로 배열을 잡고, 마디마다 맡은 길이(length)를 아래에서 위로 채운다.
- 사건 (x, +1 또는 −1, 아래 칸 번호, 위 칸 번호)를 만들어 정렬한다.
- 사건마다 넓이에 cov[1] × (x − 직전 x)를 더하고, 그 칸 범위에 +1이나 −1을 붙인다.
5단계 · 파이썬 코드
def solution(rectangles):
ys = sorted({y for _, y1, _, y2 in rectangles for y in (y1, y2)})
where = {y: i for i, y in enumerate(ys)}
m = len(ys) - 1 # 칸: ys[i] ~ ys[i + 1]
size = 1
while size < m:
size *= 2
length = [0] * (2 * size)
for i in range(m):
length[size + i] = ys[i + 1] - ys[i]
for i in range(size - 1, 0, -1):
length[i] = length[2 * i] + length[2 * i + 1]
cnt = [0] * (2 * size) # 마디를 통째로 덮는 직사각형 수
cov = [0] * (2 * size) # 마디 안에서 덮인 길이
def pull(i):
if cnt[i] > 0:
cov[i] = length[i]
elif i >= size:
cov[i] = 0
else:
cov[i] = cov[2 * i] + cov[2 * i + 1]
def update(l, r, v): # 칸 l ~ r − 1에 v를 붙인다
l += size
r += size
l0, r0 = l, r - 1
while l < r:
if l & 1:
cnt[l] += v
pull(l)
l += 1
if r & 1:
r -= 1
cnt[r] += v
pull(r)
l >>= 1
r >>= 1
for i in (l0, r0): # 바뀐 마디의 조상을 다시 계산한다
i >>= 1
while i:
pull(i)
i >>= 1
events = []
for x1, y1, x2, y2 in rectangles:
events.append((x1, 1, where[y1], where[y2]))
events.append((x2, -1, where[y1], where[y2]))
events.sort()
area, prev_x = 0, events[0][0]
for x, v, lo, hi in events:
area += cov[1] * (x - prev_x)
update(lo, hi, v)
prev_x = x
return area
where[y2]를 오른쪽 끝으로 쓴다: 칸 범위가 [where[y1], where[y2])라, y1부터 y2 바로 아래 칸까지 덮는다.- 같은 x에 사건이 여럿이면 순서는 상관없다. 그 사이의 폭이 0이라 넓이에 아무것도 더해지지 않는다.
- 재귀 대신 배열 번호로 오르내리는 판이다. 조상을 다시 계산할 때는 범위의 양 끝 잎에서 뿌리까지 두 줄만 본다.
6단계 · 실행 추적
1단계의 예다. ys = [1, 3, 4]라 칸 0은 1 ~ 3(길이 2), 칸 1은 3 ~ 4(길이 1)다.
| 사건 | 칸 범위 | 사건 전 cov[1] | 더한 넓이 | 사건 뒤 cov[1] |
|---|---|---|---|---|
| x = 0, 들어옴 (1 ~ 4) | 0 ~ 1 | 0 | 0 | 3 |
| x = 3, 들어옴 (1 ~ 3) | 0 | 3 | 3 × 3 = 9 | 3 |
| x = 4, 나감 (1 ~ 4) | 0 ~ 1 | 3 | 3 × 1 = 3 | 2 |
| x = 5, 나감 (1 ~ 3) | 0 | 2 | 2 × 1 = 2 | 0 |
x = 4에서 첫 직사각형이 나가도 칸 0은 둘째 직사각형이 아직 덮어 cnt가 1이다. 그래서 덮인 길이는 2로 남는다. 합은 14다.
7단계 · 복잡도와 흔한 실수
사건 2N개를 정렬하고 사건마다 \(O(\log N)\)이라 \(O(N \log N)\)이다. 직사각형 10만 개짜리 입력 둘(무작위, 서로 많이 겹치는 가는 직사각형)을 합쳐 2.3초쯤 걸렸다.
- y 좌표 k개를 칸 k개로 착각해, 칸 길이를 잘못 잡거나 마지막 칸을 넘어간다.
- 나감 사건에서 들어올 때와 다른 범위에 −1을 붙여 cnt가 음수가 된다.
- 덮인 길이를 “cnt > 0인 마디 길이의 합”으로 위에서 따로 구한다. 부모와 자식이 함께 덮이면 두 번 센다. cov는 마디 안에서만 계산해 위로 올린다.
- 넓이가 \(10^{18}\)까지 커진다. 파이썬은 괜찮지만 다른 언어는 64비트 정수가 필요하다.
-
프로그래머스 스쿨, “직사각형의 넓이” (https://school.programmers.co.kr/learn/courses/30/lessons/12974), 2026-10-01 조회. ↩