Level 0. 가까운 수

Level 0. 가까운 수

 

 

sort() 함수에 커스텀 비교자를 지정하여 정렬하면 쉽게 해결할 수 있지만 O(nlog n) 시간이 소요된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> array, int n)
{
    sort(array.begin(), array.end(), [n](const int a, const int b)
    {
        int distA = abs(n - a);
        int distB = abs(n - b);

        return (distA == distB) ? (a < b) : (distA < distB);
    });

    return array[0];
}

 

코드가 다소 길어지긴 했지만 직접 순회하면 O(n) 시간에 해결 가능하다.

 

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<int> array, int n)
{
    int answer = array[0];
    int dist = abs(n - array[0]);
    size_t size = array.size();

    for (int i = 1; i < size; ++i)
    {
        int t_dist = abs(n - array[i]);

        if (t_dist <= dist)
        {
            answer = (t_dist < dist) ? array[i] : min(answer, array[i]);
            dist = t_dist;
        }
    }

    return answer;
}