백준 2470번 두 용액 문제 풀이

문제 설명

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

문제를 보고 든 생각

• 안전하게 long long 타입을 사용해야겠다.
• 정렬해서 양쪽에 포인터를 두고 하나씩 간격을 좁히면 되겠다.

풀이 간단 설명

1. 용액을 오름차순으로 정렬한다.
2. 0부터 시작하는 lp, 오른쪽 끝에서 시작하는 rp
3. 둘의 차이가 음수면 lp를 하나 증가시키고 음수이면 rp를 감소시킨다.
4. 차이가 제일 적은 간격을 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct twoNum{
  ll lNum, rNum;
};

vector<ll> v;
int N;

void getInput(){
  cin >> N;
  for(int i=0; i<N; ++i){
    ll temp; cin >> temp;
    v.push_back(temp);
  }
}

twoNum getTwoNums(){
  int lp = 0, rp = N-1;
  twoNum tn = {0, 0};
  ll diff = 2000000002;

  while(lp < rp){
    ll tempDiff = v[lp] + v[rp];
    ll absTempDiff = abs(tempDiff);
    if(absTempDiff == 0){
      tn = {v[lp], v[rp]};

      return tn;
    }

    if(absTempDiff < diff){
      diff = absTempDiff;
      tn = {v[lp], v[rp]};
    }

    if(tempDiff < 0){
      ++lp;
    } else{
      --rp;
    }
  }

  return tn;
}

void solve(){
  getInput();
  sort(v.begin(), v.end());
  twoNum tn = getTwoNums();
  cout << tn.lNum << " " << tn.rNum;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}