[백준] 용액

문제 개요

오늘의 코딩 테스트 문제는 백준 2467번 '용액'이다. 산성과 알칼리성 용액을 섞어 특성값 0에 가장 가까운 용액을 만드는 문제다.

문제 분석

•

N개의 용액 (-10^9 ≤ 특성값 ≤ 10^9)

•

입력: 오름차순 정렬된 특성값

•

출력: 합이 0에 가장 가까운 두 용액의 특성값

핵심은 정렬된 배열에서 두 수의 합이 특정 값(0)에 가장 가까운 쌍을 찾는 것.

접근 방식

투 포인터 알고리즘을 사용했다. 양 끝에서 시작해 합이 0에 가까워지는 방향으로 포인터를 이동시키는 방식이다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<int> vec(N);
    for (int i = 0; i < N; i++)
        cin >> vec[i];
    
    int s=0, t=N-1;
    int min_value = 2'000'000'000;
    int index1, index2;

    while(s<t)
    {
        if (abs(vec[s]+vec[t])<min_value)
        {
            min_value = abs(vec[s]+vec[t]);
            index1 = s;
            index2 = t;
        }

        if (abs(vec[s+1]+vec[t]) < abs(vec[s]+vec[t-1]))
            s++;
        else
            t--;
    }
    
    cout << vec[index1] << ' ' << vec[index2] << endl;

    return 0;
}
C++
복사

주요 로직:

양 끝에 포인터 위치

두 포인터 값의 합 계산

최소값 갱신

다음 단계의 합이 더 0에 가까워지는 방향으로 포인터 이동

포인터가 교차할 때까지 2-4 반복

회고

이 문제가 왜 골드 레벨인지 의문이다. 정렬된 배열이 주어지고, 두 수의 합을 구하는 전형적인 투 포인터 문제다.