개념
정수 M개로 이루어진 두 배열 A와 B가 주어졌다고 가정해 봅시다. 새로운 배열 C의 i번째 원소는 d * a[i] + b[i]로 정의되며, 여기서 d는 임의의 실수입니다. 이 문제의 목표는 배열 C에 포함되는 0의 개수가 최대가 되도록 하는 d 값을 찾아 출력하고, 그때의 0의 개수도 함께 출력하는 것입니다.
입력 예시
a[] = {15, 40, 45}
b[] = {4, 5, 6}출력 예시
d의 값: -0.133333 배열 C에서 0의 개수: 1 d를 -0.133333으로 선택하면 배열 C에 0이 하나 생기며, 이것이 가능한 최댓값입니다.
해결 접근 방법
위 문제는 다음 단계를 통해 해결할 수 있습니다.
- 식 c[i] = d * a[i] + b[i]에서 c[i] = 0이 되려면 d = -b[i] / a[i]여야 하므로, 방정식을 d = -b[i]/a[i] 형태로 변형합니다.
- 해시 테이블(unordered_map)을 활용하여 각 후보 d 값(-b[i]/a[i])이 몇 번 등장하는지 세고, 가장 많이 등장하는 실숫값을 d로 결정합니다.
- 최종적으로 배열 C의 0의 개수는 '가장 많이 등장한 d의 빈도수' + '(a[i]와 b[i]가 모두 0인 쌍의 개수)'가 됩니다. a[i]와 b[i]가 모두 0인 경우에는 d 값과 무관하게 항상 0이 되기 때문입니다.
이 방법의 시간 복잡도는 O(M)이며, 공간 복잡도 역시 O(M)입니다. 부동소수점 정밀도 문제를 줄이기 위해 long double 타입을 사용하는 것이 좋습니다.
예제 코드
// 위 접근 방식을 구현한 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// d의 값을 구하고 배열 내 0의 개수를 찾는 함수
void findDandZeros1(int a[], int b[], int m){
// 해시 테이블
unordered_map<long double, int> mpp1;
int count1 = 0;
// i번째 원소에 대해 반복
for (int i = 0; i < m; i++) {
// 둘 다 0이 아닌 경우
if (b[i] != 0 && a[i] != 0) {
long double val1 = (long double)(-1.0 * b[i]) /
(long double)(a[i]);
mpp1[val1] += 1;
}
// 둘 다 0인 경우
else if (b[i] == 0 && a[i] == 0)
count1 += 1;
}
// 가장 많이 등장하는 d 찾기
int maxi1 = 0;
for (auto it : mpp1) {
maxi1 = max(it.second, maxi1);
}
// 가장 많이 등장한 d 값 출력
for (auto it : mpp1) {
if (it.second == maxi1) {
cout << "Value of d is: "
<< it.first << endl;
break;
}
}
// 0의 개수 출력
cout << "The number of zeros in array C is: "
<< maxi1 + count1;
}
// 드라이버 코드
int main(){
int a[] = { 15, 40, 45 };
int b[] = { 4, 5, 6 };
int m = sizeof(a) / sizeof(a[0]);
findDandZeros1(a, b, m);
return 0;
}실행 결과
Value of d is: -0.133333 The number of zeros in array C is: 1
위 예제에서 d = -4/15 ≈ -0.133333일 때 첫 번째 원소인 15 * (-0.133333) + 4 = 0이 되어, 배열 C에 0이 하나 생성됩니다. 세 원소 각각에 대한 d 후보 값(-4/15, -5/40, -6/45)이 모두 서로 다르므로, 어떤 d를 선택하더라도 0은 최대 하나만 만들 수 있습니다.