C++에서 함수 값이 A에 가장 가까운 숫자 찾기

함수 F(n) = P − (0.006 × n)이 정의되어 있고, 여기서 P 역시 주어진 값이라고 가정해 봅시다. 이때 정수로 이루어진 목록과 하나의 숫자 A가 주어졌을 때, 목록에 있는 수 중에서 함수 값이 A에 가장 가까운 수를 찾는 것이 문제입니다.

예를 들어 P = 12, A = 5이고 목록이 {1000, 2000}이라면 출력 결과는 1000입니다. 그 이유는 다음과 같습니다.

• F(1000) = 12 − (0.006 × 1000) = 6
• F(2000) = 12 − (0.006 × 2000) = 0

A인 5와 비교했을 때 6이 0보다 가까우므로, 해당하는 1000이 정답이 됩니다.

접근 방법

풀이 방법은 매우 직관적입니다. 목록의 각 값을 하나씩 순회하면서 해당 값 n에 대한 F(n)을 계산합니다. 그런 다음 계산된 각 함수 값 F(n)과 A 사이의 절대 차이(|F(n) − A|)를 구하고, 이 절대 차이가 최소가 되는 n을 찾으면 그것이 바로 정답입니다.

알고리즘 단계

1. 최소 차이를 저장할 변수를 무한대(INFINITY)로 초기화합니다.
2. 목록의 모든 원소에 대해 F(n) = P − (0.006 × n)을 계산합니다.
3. |F(n) − A|가 현재 저장된 최소 차이보다 작으면 최소 차이와 정답 인덱스를 갱신합니다.
4. 순회가 끝나면 저장된 인덱스에 해당하는 배열 값을 반환합니다.

구현 예제

#include<iostream>
#include<cmath>
using namespace std;
int nearestValue(int P, int A, int N, int arr[]) {
    int ans = -1;
    float temp = (float)INFINITY;
    for (int i = 0; i < N; i++) {
        float term = P - arr[i] * 0.006;
        if (abs(term-A) < temp) {
            temp = abs(term - A);
            ans = i;
        }
    }  
    return arr[ans];
}
int main() {
    int P = 12, A = 5;
    int array[] = {1000, 2000, 1001};
    int N = sizeof(array)/sizeof(array[0]);
    cout << "Nearest value is: " << nearestValue(P, A, N, array) << endl;
}

실행 결과

Nearest value is: 1001

위 예제에서는 목록에 {1000, 2000, 1001} 세 개의 값이 있으며, 각각의 함수 값은 6, 0, 5.994입니다. 이 중 A인 5에 가장 가까운 값은 5.994이므로, 최종 결과로 1001이 출력됩니다.

복잡도 분석

이 알고리즘은 목록의 모든 원소를 한 번씩만 확인하므로 시간 복잡도는 O(N)이며, 추가로 사용하는 메모리는 상수 수준이므로 공간 복잡도는 O(1)입니다. 목록이 정렬되어 있지 않아도 동작하기 때문에 어떤 입력에서도 안정적으로 사용할 수 있습니다.