이 문제에서는 N개의 구간(range)이 주어지며, 우리의 목표는 N개의 구간에서 가장 많이 등장하는 정수를 찾는 것입니다.
각 구간은 시작 값과 끝 값을 가집니다. 이 구간들에 포함된 정수 중 어떤 값이 가장 자주 나타나는지 구해야 합니다.
문제 이해를 위한 예시
입력
S1 = 1, E1 = 3
S2 = 2, E2 = 6
S3 = 3, E3 = 4
출력
3
설명
구간 [1, 3]에는 1, 2, 3이 포함되고, 구간 [2, 6]에는 2, 3, 4, 5, 6이, 구간 [3, 4]에는 3, 4가 포함됩니다. 이때 정수 3은 세 구간 모두에 등장하여 총 3번 나타나므로, 가장 많이 등장한 정수가 됩니다.
해결 접근 방법
1. 해싱(Hashing)을 이용한 방법
가장 직관적인 방법은 해시 테이블을 활용하는 것입니다. 모든 구간을 순회하면서 각 정수가 등장할 때마다 해시 테이블에 개수를 기록하고, 마지막에 개수가 가장 큰 값을 찾으면 됩니다. 하지만 구간의 길이가 길어지면 순회 비용이 커져 비효율적일 수 있습니다.
2. 차분 배열과 누적 합을 이용한 선형 시간 방법
더 효율적인 방법은 차분 배열(difference array)을 사용하는 것입니다. 각 구간의 시작 인덱스에는 1을 더하고, 끝 값의 다음 인덱스에는 1을 뺍니다. 이후 배열 전체에 대해 누적 합(prefix sum)을 계산하면, 각 인덱스 위치의 값이 곧 해당 정수가 속한 구간의 개수가 됩니다. 누적 합이 최대가 되는 인덱스가 바로 우리가 찾는 정수입니다.
예제 코드
다음 프로그램은 위 해결 방법의 동작을 보여줍니다.
#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;
int findMaxOccrEle(int L[], int R[], int n){
int occurrenceCount[MAX];
memset(occurrenceCount, 0, sizeof occurrenceCount);
int maxi = -1;
// 각 구간의 시작점에서 +1, 끝점 다음 위치에서 -1
for (int i = 0; i < n; i++) {
occurrenceCount[L[i]] += 1;
occurrenceCount[R[i] + 1] -= 1;
if(R[i] > maxi){
maxi = R[i];
}
}
// 누적 합을 계산하며 최대 등장 횟수와 해당 인덱스를 추적
int prefSum = occurrenceCount[0], maxEleIndex = 0;
for (int i = 1; i <= maxi; i++) {
occurrenceCount[i] += occurrenceCount[i - 1];
if (prefSum < occurrenceCount[i]) {
prefSum = occurrenceCount[i];
maxEleIndex = i;
}
}
return maxEleIndex;
}
int main(){
int L[] = { 1, 2, 3 };
int R[] = { 3, 6, 4 };
int n = sizeof(L) / sizeof(L[0]);
cout<<"범위에서 가장 많이 등장하는 정수는 "<<findMaxOccrEle(L, R, n);
return 0;
}
출력 결과
범위에서 가장 많이 등장하는 정수는 3
복잡도 분석
시간 복잡도: O(n + MAX) — 구간을 한 번씩 순회하고(O(n)), 누적 합 계산 시 최대값까지 순회하기 때문입니다.
공간 복잡도: O(MAX) — 카운트 배열을 저장하기 위해 추가 공간이 필요합니다.
이처럼 차분 배열과 누적 합을 활용하면 각 구간의 모든 원소를 일일이 세지 않고도 가장 많이 등장하는 정수를 효율적으로 찾을 수 있습니다.