[개쉬운 풀이] 백준 2467 용액 (10일차) - 이분 탐색X

https://www.acmicpc.net/problem/2467

문제

 

 

생각

사실 문제의 의도는 이분탐색이다. 그러나 두 값을 더해서 0에 가장 가까운 용액을 찾는 문제에서 영감을 얻었다.

우리는 사전문제 등 문자열을 비교할때 보통 sort를 한 다음, 양 옆 문자들만 비교한다. 이를 착안하여 문제를 풀었다.

 

두 용액이 0에 가장 가까우려면 두 용액의 숫자 크기가 거의 비슷해야한다. 따라서 두 용액을 절대값 처리를 통해 정렬해주었다.

[-99, -2, -1, 4, 98] => [1, 2, 4, 98, 99] 이렇게 되면 한 눈에 98과 99가 부호가 다르다면 정답임을 알 수 있다.

 

따라서 절대값 처리와 함께 원래의 부호도 같이 저장하여 정렬하였다.

 

마지막으로, 출력할 때 더 작은 값을 기준으로 출력해야한다.

 

풀이

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

int N;
vector<pair<ll, bool>> v; //양수면 true, 음수면 false

void input(){
  cin >> N;
	for(int i = 0; i < N; i++){
		ll tmp;
		bool sign = true;
		cin >> tmp;
		if(tmp < 0){
			sign = false;
		}
		v.push_back(make_pair(abs(tmp), sign));
	}
}

bool cmp(pair<ll,bool> A, pair<ll,bool> B){
	return A.first < B.first;
}

void sol(){
	sort(v.begin(), v.end(), cmp);

	ll min_res = 1e9 * 3; //두 값의 합은 1e9 + 1e9가 최대가 될 수 있으므로.
	ll ans1, ans2;

	for(int i = 0; i < v.size()-1; i++){
		auto x1 = v[i];
		auto x2 = v[i+1];
		ll res;
		if(x1.second == x2.second){ //같은 부호
			res = abs(x1.first + x2.first);
		}
		else{ //다른 부호
			res = abs(x1.first - x2.first);
		}

		if(res < min_res){
			min_res = res;
            //원래 상태로 저장
			ans1 = (x1.second) ? x1.first : x1.first*(-1); 
			ans2 = (x2.second) ? x2.first : x2.first*(-1);
		}
	}

	if(ans1 < ans2) cout << ans1 << " " << ans2 << endl;
	else cout << ans2 << " " << ans1 << endl;
}

int main(){
	input();
	sol();

	return 0;
}