백준 2467 용액 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/2467

아이디어

• 각 숫자를 순회하면서 0에 가까운 수를 찾으면
  • O(N^2) = 1e10 > 시간초과
• 한 숫자를 정하고 나머지 숫자에 대해서 반대값을 이진탐색
  • O(N * lgN)
• lower ? upper ?
  • lower로 찾고, 만약 0보다 클경우, 하나 인덱스 뺀것도 같이 계산해주자
• 이진탐색 범위
  • 오름차순이기 때문에, 자기 자신의 다음위치만 찾으면 됨
  • 자기자신 이전에 있을 경우는 어짜피 쌍으로되기때문에 이전에서 찾아줌

시간복잡도 계산

• 모든 숫자에 대해서 : O(N)
• 이진탐색 진행 : O(lgN)
• 시간복잡도 : O(N*lgN) : 1e5 * 20 = 2e6

인트 계산

• 최소값 2개 더할경우 : -2e9
• 최대값 2개 더할경우 : 2e9
• 인트 사용 가능

코드

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> nums;
 
int binsearch(int st, int en, int tar) {
    if(st==en) return st;
    
    int mid = (st+en)/2;
    if(nums[mid] < tar) return binsearch(mid+1, en, tar);
    else return binsearch(st, mid, tar);
    
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int a; cin >> a;
        nums.push_back(a);
    }
    
    int minv =2e9+10;
    int fn = -1;
    int sn = -1;
    
    // 모든 숫자에 대해서, 마지막은 빼주기
    for(int i=0; i<N-1; i++) {
        int eachNum = nums[i];
        
        // eachNum에 반대되는값을 이진탐색
        int target = eachNum * -1;
        int idx = binsearch(i+1,nums.size()-1, target);
        
        // idx 이전값이랑 비교할때, 같은 값이 아닌지 주의
        if(idx >0 && idx-1 != i) {
            if( abs(nums[idx] + eachNum) > abs(nums[idx-1] + eachNum)) idx = idx-1;
        }
        
        if(minv > abs(nums[idx] + eachNum)) {
            minv =abs(nums[idx] + eachNum);
            fn = eachNum;
            sn = nums[idx];
        }
        
    }
    
    if(fn > sn) cout << sn << ' ' << fn << '\n';
    else cout << fn << ' ' << sn << '\n';
    
    
    
    return 0;
}
 

문제유형

• 이진탐색 - 리스트 내의 값으로 이진탐색
  • 리스트 안에 있는 값중 하나로, 자기와 반대되는 값을 탐색
  • 자기 자신부터 끝까지 이진탐색 수행
  • 마지막 원소는 이진탐색 해주지 않음
  • 쌍을 찾는것이기 때문에 마지막 원소는 찾지 않아도됨