baekjoon 2467:용액

baekjoon 2467 용액

2467번 용액

접근

처음에는 2개를 고를 수 잇는 경우를 다 따지는 방식을 써봤는데 100,000C2는 1초를 아득히 초과했다.
그 다음에는 수 범위만큼 배열을 만들어 두고 모든 수에 대해 자기에 -1을 곱한수와 가장 가까운 수를 저장해두고 시작하는 방법을 사용했다.
그런데 수 범위가 1,000,000,000까지라 메모리 초과가 발생했다.
결국 자기에 -1을 곱한수와 가장 가까운 수를 이진탐색으로 logn안에 찾는 방식을 써야했다.
일치하는 값이 아닌 가까운 수를 탐색하는 것이라 조금 알고리즘을 변형시켜야했다.
그런데 지금 생각해보니 upper_bound, lower_bound함수를 사용했었다면 훨씬 쉽게 구할 수 있었다는 생각이 들긴한다.
실제로 플레 lis 문제를 풀 때 위 함수를 사용했으니 거기서 자세히 함수 사용법을 알아보자.

코드

#include <iostream>
#include <array>
#include <vector>
using namespace std;
int n;
vector<int> v;
int binarySearchSimilar(int target){
  int left = 0;
  int right = n-1;
  int mid = (left + right)/2;
  while(left <= right){
    // cout << "(" << left << " " << mid << " " << right << ")\n";
    if(v[mid] == target) return mid;
    // if(left == right) return left;
    if(left + 1 == right){
      if(v[left] == target) return left;
      if(v[right] == target) return right;
      if(abs(v[left] - target) < abs(v[right] - target)) return left;
      return right;
    }
    if(v[mid] > target){
      right = mid;
      mid = (left + right)/2;
      continue;
    }
    if(v[mid] < target){
      left = mid;
      mid = (left + right)/2;
      continue;
    }
  }
  return -1;
};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++){
    int a; cin >> a;
    v.push_back(a);
  }
  if(v[0] >= 0){
    //all positive
    cout << v[0] << " " << v[1];
    return 0;
  }
  if(v[n-1] <= 0){
    //all negative
    cout << v[n-2] << " " << v[n-1];
    return 0;
  }
  
  //all positive or negative removed
  pair<int, int> globalAns = {1e9, 1e9};
  for(int i = 0; i < n; i++){
    int a = v[i];
    int bIndex = binarySearchSimilar(-1*a);
    pair<int, int> tempAns;
    if(v[bIndex] == a){
      if(bIndex == 0){
        tempAns = {v[bIndex], v[bIndex+1]};
      }
      else if(bIndex == n-1){
        tempAns = {v[bIndex-1], v[bIndex]};
      }
      else{
        if(abs(a + v[bIndex-1]) < abs(a + v[bIndex+1])){
          tempAns.first = min(a, v[bIndex-1]);
          tempAns.second = max(a, v[bIndex-1]);
        }
        else{
          tempAns.first = min(a, v[bIndex+1]);
          tempAns.second = max(a, v[bIndex+1]);
        }
      }
    }
    else{
      tempAns.first = min(a, v[bIndex]);
      tempAns.second = max(a, v[bIndex]);
    }
    // cout << tempAns.first << " " << tempAns.second << endl;
    if(abs(tempAns.first + tempAns.second) < abs(globalAns.first + globalAns.second)){
      globalAns = tempAns;
    }
  }
  cout << globalAns.first << " " << globalAns.second;
  
  return 0;
}

배운 점

이분탐색으로 시간을 줄여보자!