2467 용액

문제 링크

• 나의 풀이

전체 수를 순회하며 (현재 수 * -1)를 이분탐색으로 찾는다. 대상 수를 찾지 못하면 upperbound, lowerbound 이용해 가장 작은 합을 탐색한다. 하지만 2번 씩 이분탐색하여 시간을 초과하게 되었다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <climits>

using namespace std;

int nums[100000], N;

pair<int, int> solve()
{
    pair<int, int> ret;
    
    int val = INT_MAX, left, right;

    for (int i = 0; i < N - 1 ; i++)
    {
        int st = i + 1, ed = N - 1, mid;
        int tg = -1 * nums[i];

        while (st < ed)
        {
            mid = (st + ed + 1) / 2;
            if (nums[mid] == tg)
            {
                if (i > mid)
                    ret = make_pair(mid, i);
                else if (i < mid)
                    ret = make_pair(i, mid);
                else
                    continue;
                return ret;
            }

            else if (nums[mid] > tg)
                ed = mid - 1;
            else
                st = mid;
        }
        left = st;

        st = 0, ed = N - 1;
        while (st < ed)
        {
            mid = (st + ed) / 2;
            if (nums[mid] == tg)
            {
                if (i > mid)
                    ret = make_pair(mid, i);
                else if (i < mid)
                    ret = make_pair(i, mid);
                else
                    continue;
                return ret;
            }

            else if (nums[mid] < tg)
                st = mid + 1;
            else
                ed = mid;
        }
        right = st;

        cout << i << " : " << left << ", " << right << "\n";

        if (val > abs(nums[i] + nums[left]) || val > abs(nums[i] + nums[right]))
        {
            int n;
            if (abs(nums[i] + nums[left]) < abs(nums[i] + nums[right]))
                n = left;
            else
                n = right;

            if (i == n)
                n = left == n ? right : left;

            if (abs(nums[i] + nums[n]) > val)
                continue;
            val = abs(nums[i] + nums[n]);
            ret = i < n ? make_pair(i, n) : make_pair(n, i);
            
        }
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for(int i = 0; i < N; i++)
        cin >> nums[i];

    pair<int, int> ans = solve();

    cout << nums[ans.first] << " " << nums[ans.second] << "\n";
 }

• 다른 사람 풀이

합계값을 기준으로 이분탐색을 하여 0과 가장 근접한 값을 탐색하는 방식으로 작성했다. 이분탐색 알고리즘을 해당 수를 찾는것만 생각하지 말고 다양한 방법으로 응용하도록 노력하자.

#include <iostream>
#include <climits>
#include <algorithm>
#include <string>

using namespace std;

int N, nums[100001];

pair<int,int> solve()
{
    pair<int, int> ret;
    int minSum = INT_MAX, sum, st, ed, mid;

    for (int i = 0; i < N - 1; i++)
    {
        st = i + 1, ed = N - 1;
        while (st <= ed)
        {
            mid = (st + ed) / 2;
            sum = nums[i] + nums[mid];
            if (minSum > abs(sum))
            {
                minSum = abs(sum);
                ret = make_pair(nums[i], nums[mid]);
            }
            if (sum > 0)
                ed = mid - 1;
            else
                st = mid + 1;
        }
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> nums[i];

    sort(nums, nums + N);

    pair<int, int> result = solve();
    cout << result.first << " " << result.second << "\n";
}

• 또 다른 풀이

이분 탐색 말고 Two Pointer 알고리즘을 이용하여 답을 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;

    vector<int> v(N);
    for (int i = 0; i < N; i++)
    {
        cin >> v[i];
    }

    sort(v.begin(), v.end());

    int i = 0, j = v.size() - 1;
    int total = 2e9;
    pair<int, int> result;

    while (i < j)
    {
        int a = v[i];
        int b = v[j];

        if (abs(a + b) < total)
        {
            total = abs(a + b);

            result.first = v[i];
            result.second = v[j];
        }

        if (a + b < 0)
        {
            i++;
        }
        else
        {
            j--;
        }
    }

    cout << result.first << " " << result.second << "\n";

    return 0;
}