문제 개요
주어진 점들을 여러 선분에 배정했을 때, 적어도 하나의 점을 포함하게 되는 선분의 개수를 최대화하는 것이 이번 글에서 다룰 문제입니다.
크기가 n1인 배열 a1[]과 두 정수 A, B가 주어집니다. 배열 a1[]의 각 원소를 이용해 총 n1개의 선분을 만들 수 있으며, i번째 선분은 시작점 a1[i] – A, 끝점 a1[i] + B로 정의됩니다.
또 다른 배열 a2[]에는 n2개의 점이 주어집니다. 이 점들을 선분에 배정하여, 점이 하나라도 배정된 선분의 개수가 최대가 되도록 만들어야 합니다. 단, 하나의 점은 하나의 선분에만 배정할 수 있습니다.
예제로 이해하기
입력:
a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2
출력:
1
설명: a1[i] – A부터 a1[i] + B까지의 구간으로 만들 수 있는 선분은 (0, 3), (3, 6), (4, 7)입니다. 첫 번째 점 2는 첫 번째 선분 (0, 3)에 배정할 수 있지만, 두 번째 점 8은 어떤 선분에도 속하지 못합니다. 따라서 점이 배정된 선분은 1개뿐이므로 출력은 1이 됩니다.
입력:
a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1
출력:
4
이 경우 선분 (1, 2), (2, 3), (3, 4), (4, 5), (6, 7), (7, 8)이 만들어지며, 네 점 모두 각각 서로 다른 선분에 배정할 수 있으므로 정답은 4입니다.
알고리즘 접근 방식
두 배열을 정렬한 뒤 투 포인터(two pointer) 방식으로 선분과 점을 순서대로 비교하면 그리디하게 최적의 배정을 찾을 수 있습니다. 구체적인 절차는 다음과 같습니다.
- main 함수에서 벡터 a1, a2와 정수 A, B를 초기화합니다.
- 변수 n1, n2를 만들어 각각 벡터 a1, a2의 크기를 저장합니다.
- Max() 함수에서 먼저 두 벡터 a1과 a2를 오름차순으로 정렬합니다.
- 배열 a2를 가리킬 인덱스 j와 최종 답을 저장할 ans를 0으로 초기화합니다.
- i가 0부터 n1 미만일 때까지 for 반복문을 수행합니다.
- for 루프 내부에서 조건 j < n2를 만족하는 동안 while 루프를 실행합니다.
- a1[i] + B < a2[j]라면 현재 선분의 끝점이 해당 점보다 앞서 있으므로 이 선분에는 점을 배정할 수 없습니다. 이 경우 while 루프를 종료(break)하고 다음 선분으로 넘어갑니다.
- 반대로 a2[j] >= a1[i] - A 이면서 a2[j] <= a1[i] + B라면 점이 현재 선분 범위 안에 있는 것이므로 ans와 j를 각각 1 증가시킨 뒤 while 루프를 종료합니다.
- 위 어느 조건에도 해당하지 않으면, 즉 현재 점이 아직 선분 시작점보다 앞에 있다면 j만 1 증가시켜 다음 점을 검사합니다.
- 모든 탐색이 끝나면 ans를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B){
// a1과 a2 정렬
sort(a1.begin(), a1.end());
sort(a2.begin(), a2.end());
int j = 0;
int ans = 0;
for (int i = 0; i < n1; i++){
// 배정 가능한 점 탐색
while (j < n2){
/* 선분의 끝점이 현재 점보다
작은 경우 */
if (a1[i] + B < a2[j])
break;
// 점이 선분 범위 내에 있는 경우
if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B){
ans++;
j++;
break;
}
else
j++;
}
}
return ans;
}
// main 함수
int main(){
int A = 0, B = 1;
vector<int> a1 = { 1, 2, 3, 4, 6, 7 };
int n1 = a1.size();
vector<int> a2 = { 2, 5, 6, 8 };
int n2 = a2.size();
cout << Max(a1, a2, n1, n2, A, B);
return 0;
}
출력:
4
시간 복잡도
두 배열을 정렬하는 데 O(n1 log n1 + n2 log n2)의 시간이 걸리고, 정렬 이후 투 포인터 스캔은 각 원소를 최대 한 번씩만 방문하므로 O(n1 + n2)에 완료됩니다. 따라서 전체 시간 복잡도는 O(n1 log n1 + n2 log n2)이며, 입력 크기가 커져도 효율적으로 동작합니다.