BOJ 2467 - 용액

문제 요약

N개의 정수 배열(오름차순 정렬)에서 두 원소의 합이 0에 가장 가까운 쌍을 구하는 문제.

첫 접근 - O(N²) 브루트포스

처음엔 그냥 이중 루프로 모든 쌍을 비교했다.

for(int i = 0; i < N; i++){
    for(int j = i+1; j < N; j++){
        if(abs(arr[i] + arr[j]) < res){
            res = abs(arr[i] + arr[j]);
            a = arr[i]; b = arr[j];
        }
    }
}

답은 맞는데 시간초과. N이 최대 100,000이라 O(N²)은 당연히 터진다.

핵심 아이디어 - 두 포인터

배열이 정렬되어 있다는 조건을 활용한다.

• 양 끝에 포인터 l, r을 놓고 시작
• arr[l] + arr[r] > 0 → 합이 너무 크다 → r--
• arr[l] + arr[r] < 0 → 합이 너무 작다 → l++
• arr[l] + arr[r] == 0 → 즉시 종료

이렇게 하면 O(N)으로 해결된다.

왜 이게 되냐면, 정렬된 배열에서 r을 줄이면 합이 작아지고 l을 키우면 합이 커진다는 게 보장되기 때문.

최종 코드

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int main() {
    int N;
    cin >> N;
    
    vector<int> arr(N);
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    
    int l = 0;
    int r = N-1;
    int diff = abs(arr[l] + arr[r]);
    int ll = 0, rr = N-1;

    while(l < r) {
        if(diff > abs(arr[l] + arr[r])){
            diff = abs(arr[l] + arr[r]);
            ll = l;
            rr = r;
        }
        if(arr[l] + arr[r] == 0){
            ll = l;
            rr = r;
            break;
        }
        else if(arr[l] + arr[r] > 0){
            r--;
        }
        else if(arr[l] + arr[r] < 0){
            l++;
        }
    }
    cout << arr[ll] << ' ' << arr[rr];
    return 0;
}

삽질 포인트

• min을 변수명으로 쓰면 std::min이랑 충돌 → 컴파일 에러
• diff (현재 최솟값) 저장할 때 절댓값으로 저장해야 함. 음수로 저장하면 이후 비교가 망가짐
• ll, rr 초기화 안 하면 운 나쁘면 out of bounds

시간복잡도

• O(N) — 포인터가 각각 한 방향으로만 이동하므로 총 이동 횟수는 N을 넘지 않음