문제 정의
정렬되지 않은 두 배열 arr1[]과 arr2[]가 주어졌다고 가정해 봅시다. 우리가 해야 할 작업은 arr1[]의 각 요소에 대해, arr2[] 안에서 그 요소보다 작거나 같은 값이 몇 개 있는지 세는 것입니다. 단, 두 배열에는 중복된 값이 포함될 수 있다는 점을 유의해야 합니다.
예제 입력
N = 6
M = 9
arr1[N] = {1, 2, 5, 0, 6, 3}
arr2[M] = {0, 0, 1, 2, 1, 3, 4, 6, 8}예제 출력
4 5 7 2 8 6
출력 결과를 살펴보면, arr1의 첫 번째 요소 1보다 작거나 같은 arr2의 요소는 {0, 0, 1, 1}로 총 4개이고, 두 번째 요소 2보다 작거나 같은 요소는 {0, 0, 1, 2, 1}로 총 5개입니다. 나머지 요소도 같은 방식으로 계산됩니다.
문제 해결 접근 방식
이 문제를 효율적으로 해결하려면 arr2[]를 먼저 오름차순으로 정렬한 뒤, 이진 탐색(Binary Search)을 활용하는 것이 핵심입니다. 정렬된 배열에서 이진 탐색을 수행하면 특정 값보다 작거나 같은 요소의 개수를 O(log M) 시간에 빠르게 구할 수 있습니다.
풀이 단계
두 배열의 크기 m과 n, 그리고 배열의 요소들을 입력받습니다.
countInSecond(int *arr1, int *arr2, int m, int n) 함수가 두 배열과 각각의 크기를 매개변수로 받아 결과를 계산합니다.
먼저 arr2[]를 오름차순으로 정렬합니다.
arr1[]의 모든 요소를 순회하면서, 이진 탐색으로 arr2[] 내에서 해당 요소보다 작거나 같은 마지막 위치를 찾습니다.
탐색이 끝난 후의 위치 인덱스 + 1이 곧 조건을 만족하는 요소의 개수이므로 이를 출력합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
void countInSecond(int *nums1, int *nums2, int m, int n){
sort(nums2, nums2 + n);
for(int i = 0; i < m; i++){
int s = 0;
int e = n - 1;
while(s <= e){
int mid = (s + e) / 2;
if(nums2[mid] <= nums1[i])
s = mid + 1;
else
e = mid - 1;
}
cout << e + 1 << " ";
}
}
int main(){
int m = 6;
int n = 9;
int arr1[m] = {1, 2, 5, 0, 6, 3};
int arr2[n] = {0, 0, 1, 2, 1, 3, 4, 6, 8};
countInSecond(arr1, arr2, m, n);
return 0;
}코드 동작 원리
이진 탐색 과정에서 nums2[mid]가 현재 검사 중인 nums1[i]보다 작거나 같으면 탐색 범위의 시작점 s를 mid + 1로 이동하고, 그렇지 않으면 끝점 e를 mid - 1로 이동시킵니다. 반복문이 종료되면 변수 e는 'nums1[i]보다 작거나 같은 요소들 중 마지막 인덱스'를 가리키게 되므로, e + 1이 곧 조건을 만족하는 요소의 총 개수가 됩니다.
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
4 5 7 2 8 6
즉, arr1의 각 요소보다 작거나 같은 arr2의 요소 개수는 순서대로 {4, 5, 7, 2, 8, 6}입니다.
시간 복잡도 분석
arr2[]를 정렬하는 데 O(M log M), 각 요소마다 이진 탐색을 수행하는 데 O(log M)씩 걸리므로, 전체 시간 복잡도는 O(M log M + N log M)입니다. 단순히 이중 반복문으로 매번 배열 전체를 확인하는 O(N × M) 방식에 비해 훨씬 효율적이므로, 데이터 크기가 클 때 특히 유용한 접근 방법입니다.