[백준] 2467: 용액, 3151: 합이 0 - 이분 탐색을 활용한 숫자의 합을 0으로 만들기

https://www.acmicpc.net/problem/2467

https://www.acmicpc.net/problem/3151

---

용액을 먼저 풀어보고 합이 0을 풀어보는 것을 추천한다.

 

백준 2467: 용액

용액은 간단하게 합이 0과 가장 가까운 index를 찾으면 된다.

arr [i]를 기준으로 찾으면 될 것 같은데 결론부터 말하자면 arr [i]와 합이 0과 가장 가까워지는 index를 찾으려면 -arr [i]를 lower_bound() 함수에 적용하면 된다. lower_bound(~~, ~~, -arr [i])의 결과는 -arr [i] 이상인 값이 될 테고 그 값을 arr [k]라 하자.

arr [k]는 -arr [i]가 될 수도 있고 그 값보다 클 수도 있다. 또, arr [k-1]은 -arr [i] 보다 작은 값인데, 정말 근소하게 작을 수 있다. 문제 조건을 보면 서로 다른 두 용액을 찾아야 한다. 따라서 arr [k]가 -arr [i]와 같을 수 있으므로 같은 경우는 해당 용액을 건너뛰고 arr [k+1]을 체크해야 한다. 이 논리 그대로 arr [k-1], arr [k], arr [k+1]을 체크해 주면 된다.

/** BS 2467 용액 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;
int arr[100100];

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

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    // arr[i]와 합이 0에 가장 가까운 index를 찾아보자.
    //-arr[i] 이상인 값 중 가장 작은 값을 k라 하면
    // k, k-1, k+1 중에 답이 될 수 있는데, arr[i] == k 면 안된다.

    int ans1 = 1e9 + 1, ans2 = 1e9 + 1;
    for (int i = 0; i < n; i++)
    {
        // arr[i]에 대해 답이 될 수 있는 후보 체크
        int k = lower_bound(arr, arr + n, -arr[i]) - arr;
        // arr[i], arr[k-1] 체크
        if (i != k - 1 && k - 1 >= 0 && abs(arr[i] + arr[k - 1]) < abs(ans1 + ans2))
        {
            ans1 = arr[i];
            ans2 = arr[k - 1];
        }
        // arr[i], arr[k] 체크
        if (i != k && k < n && abs(arr[i] + arr[k]) < abs(ans1 + ans2))
        {
            ans1 = arr[i];
            ans2 = arr[k];
        }
        // arr[i], arr[k+1] 체크
        if (i != k + 1 && k + 1 < n && abs(arr[i] + arr[k + 1]) < abs(ans1 + ans2))
        {
            ans1 = arr[i];
            ans2 = arr[k + 1];
        }
    }
    if (ans1 > ans2)
        cout << ans2 << ' ' << ans1 << '\n';
    else
        cout << ans1 << ' ' << ans2 << '\n';
}

최대 값은 안전하게 1e9 + 1로 사용하자! 

코드를 짜 두고 Edge case도 생각해 보자.

Edge cases

크게 생각나는 edge case는 arr [k-1], arr [k], arr [k+1]이 각각 선택되는 경우이다. 차례대로 -9 8 11 20 / -10 -8 -3 3 20 / -10 -8 -5 -4 -3 -1 / 이 정도이다. Edge case를 찾는 과정은 아직 연습 중이라 좀 부족한 느낌이 든다.

---

백준 3151: 합이 0

이번에는 세 수의 합이 0이 되어야 한다. 아무리 생각해도 뭔가 어떻게 어떻게 해서 세 수의 합을 한 번의 반복문으로 계산하는 방식은 도저히 안 떠오르고 일단 두 수의 합을 구해놓고 두 수의 합을 또 구하는 방식을 생각해 봤다. (arr [i] + arr [j])를 구하고 그 값과 합이 0이 되는 값을 찾는 것이다.

 

똑같이 k=lower_bound(arr, arr+n, -(arr [i]+arr [j]) 을 구하면 되는데, 세 가지 문제점이 존재한다.

먼저, -3 -4 7 7 7 7 7 10처럼 합이 0이 되는 수가 여러 개 존재하는 경우이다. 이 경우는 upper_bound를 쓰면 log(N)으로 해결할 수 있다. 간단하게 7 초과인 index - 7 이상인 index => 숫자 7의 개수가 되는 것이다.

 

다음은 -4 2 7처럼 -4, 4의 합이 -2이고 -2의 lower_bound가 2가 나와서 중복이 발생하는 경우이다. 이 부분이 오히려 까다로웠는데 반복문을 한 번이라도 더 쓰면 시간 초과에 걸릴 것이고 복잡하게 해결하면 안 된다는 점이 발목을 잡았다. 답을 구하는 과정을 생각해 보면, i, j는 점점점점 뒤로 이동하면서 답을 구하게 될 것이다. 즉, j+1 index부터 답이 될 수 있다. 따라서 lower_bound, upper_bound의 시작 index를 arr이 아닌 arr+j+1로 설정하면 해결된다.

 

마지막으로 답이 21억을 넘을 수 있다는 점이다. 놓치고 가기 쉬운데 프로그래머스에서 나오는 코테는 틀렸다고 알려주지도 않는다... 반드시 까먹지 말고 계산해 보자. 답을 long long으로 선언해야 한다!

/** bs 3151 합이 0 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;
int arr[10005];

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

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    sort(arr, arr + n);

    long long ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            //(i+j) 값의 lower bound -> 합이 0이 될 수 있는 후보
            long long k = lower_bound(arr + j + 1, arr + n, -(arr[i] + arr[j])) - arr;
            if (arr[i] + arr[j] + arr[k] != 0)
                continue;
            // k번째 값을 더하면 0이 되는 것을 확인. 하지만 여러 개 있을 수 있으므로 upper bound로 확인해야 함.
            long long u = upper_bound(arr + j + 1, arr + n, -(arr[i] + arr[j])) - arr;
            ans += u - k;
        }
    }
    cout << ans << '\n';
}

 

Edge cases

-4 0 1 2 3 3 -> i + j (-4 + 2)가 또 2가 되어서 중복이 발생하는 경우 체크

-4 0 1 3 3 3 -> i + j (-4 + 2)가 음수인 경우 체크

이 정도밖에 안 떠오른다..