문제 소개
정수 리스트의 리스트, 즉 구간(interval) 목록이 주어진다고 가정해 봅시다. 각 구간은 [start, end] 형태를 가집니다. 이때 이 구간들 안에서 가장 많이 등장하는 숫자를 찾아야 합니다. 만약 빈도수가 같은 숫자가 여러 개 있다면, 그중 가장 작은 숫자를 반환하면 됩니다.
예를 들어 입력이 [[2, 5], [4, 6], [7, 10], [8, 10]]이라면 출력은 4가 됩니다. 왜냐하면 4는 세 개의 구간 [2,5], [4,6]에 포함되어 가장 높은 빈도를 기록하기 때문입니다.
해결 접근 방식: 스위핑(Sweeping) 기법
이 문제는 차분 배열(difference map)과 누적 합을 활용한 스위핑 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 구간의 시작점에서는 해당 숫자가 등장하기 시작하고, 끝점 + 1에서는 더 이상 등장하지 않습니다.
- 따라서 시작점에는 +1을, 끝점 + 1에는 -1을 기록한 뒤, 정렬된 순서대로 값을 누적하면 각 지점에서의 실제 등장 횟수를 알 수 있습니다.
알고리즘 단계
- 정렬된 맵(map) 하나를 정의합니다.
- 최대 빈도수를 저장할
cnt = 0, 결과값을 저장할val = 0으로 초기화합니다. - 각 구간에 대해 시작점
it[0]의 값을 1 증가시키고, 끝점 + 1인it[1] + 1의 값을 1 감소시킵니다. - 누적 변수
last = 0을 선언합니다. - 맵의 모든 키를 오름차순으로 순회하면서 값을 누적합니다. 누적값이
cnt보다 크면cnt와val을 갱신합니다. - 순회가 끝나면
val을 반환합니다.
std::map은 키를 자동으로 오름차순 정렬해 주기 때문에, 동률일 경우 항상 더 작은 숫자가 먼저 발견되어 자연스럽게 조건을 만족하게 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>>& x) {
map <int, int> m;
int cnt = 0;
int val = 0;
for(auto& it : x){
m[it[0]]++;
m[it[1] + 1]--;
}
int last = 0;
for(auto& it : m){
last += it.second;
if(last > cnt){
cnt = last;
val = it.first;
}
}
return val;
}
};
main() {
Solution ob;
vector<vector<int>> v = {{2, 5},{4, 6},{7, 10},{8, 10}};
cout << ob.solve(v);
}입력
{{2, 5}, {4, 6}, {7, 10}, {8, 10}}출력
4
동작 원리 상세 설명
위 입력을 기준으로 맵의 변화를 살펴보면 다음과 같습니다.
- [2, 5]: m[2] += 1, m[6] -= 1
- [4, 6]: m[4] += 1, m[7] -= 1
- [7, 10]: m[7] += 1, m[11] -= 1
- [8, 10]: m[8] += 1, m[11] -= 1
키 순서대로 누적하면: 2 → 1, 4 → 2, 6 → 1, 7 → 1, 8 → 2, 11 → 0이 됩니다. 여기서 최대 누적값 2는 처음으로 4에서 나타나므로, 정답은 4입니다.
시간 복잡도 분석
n개의 구간이 있을 때, 맵 삽입 연산에 O(n log n), 순회에 O(n log n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 맵에 저장되는 고유 좌표 수에 비례하여 O(n)입니다. 구간의 범위가 매우 클 때도 배열 대신 맵을 사용하면 메모리를 절약할 수 있다는 장점이 있습니다.