호되게 쳐맞았던 면접 주간이 끝나고,, 네이버 코테가 토요일이다!! 알골 시급!!
오늘 풀어본 문제는 BOJ 2467 용액 이다. 이분탐색 문제라고 해서 들어갔는데 막상 투포인터가 먼저 떠올라서 투포인터로 먼저 풀고 다시 이분탐색으로 풀어보았다.
BOJ 2467 용액
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.
입출력
[입력]
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
[출력]
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
나의 풀이
투포인터
문제를 보자마자 생각 난 방법은 투포인터 이다.
투포인터는 배열이 정렬된 상태에서 사용해야 하지만 입력 조건에 보면 오름차순으로 정렬되어 입력된다길래 따로 정렬을 수행할 필요는 없었다.
용액 배열 안에서 left, right 포인터를 두고 두 변수는 각각 left = 0 right = numbers.size()-1 에서 시작한다.
두 포인터가 가리키는 두 수의 합sum이 0에서 가까우면 정답을 갱신하고 sum이 0보다 작다면 left++, 0보다 크다면 right-- 를 수행한다.
두 포인터 left와 right 가 역전될 때 까지 탐색을 수행하면 총 O(N)의 시간 내에 정답을 구할 수 있다.
이진 탑색
이분 탐색을 연습하려 했던 문제였지만 왠일인지 이분 탐색 활용은 생각이 나지 않았다.
레퍼런스를 조금 찾아봤고 방법은 오름차순으로 기준 용액을 잡은 뒤 해당 용액과 가장 0에 가까운 합을 내는 다른 용액을 찾는 과정을 이진 탐색을 통해 찾는 것이었다.
총 N개의 용액을 i = 0 ~ N-2 번째 용액을 기준으로 하고 i+1 ~ N-1 범위 내에서 두 변수 left, right 의 중간 위치 mid 가 가리키는 용액과의 합을 계산한다.
이후 해당 합이 0에 더 가까우면 갱신하고, 합이 0보다 작다면 left = mid+1, 0보다 크다면 right=mid-1 을 수행해 범위를 절반씩 뚝뚝 줄여 나간다.
이 경우엔 left, right 가 같은 경우에도 0에 더 가까운 합이 될 수 있기 때문에 left<=right 일때까지 탐색을 진행하면 총 O(NlogN) 시간 안에 정답을 도출할 수 있다.
코드
투포인터
#include <iostream>
#include <vector>
#include <cstdlib>
#include <climits>
// boj 2467 용액, 투포인터 사용, 골드 5
using namespace std;
vector<long long> numbers;
pair<long long, long long> getBestPair(){
pair<long long, long long> answer;
int left = 0, right = numbers.size()-1;
long long best_sum = LLONG_MAX;
while (left<right){
int sum = numbers[left] + numbers[right];
if (abs(sum) < best_sum){
best_sum = abs(sum);
answer.first = numbers[left];
answer.second = numbers[right];
}
if(sum < 0) left++;
else right--;
}
return answer;
}
int main() {
int N;
cin>>N;
numbers.assign(N, 0);
for (int i = 0; i < N; ++i) cin>>numbers[i];
pair<long long,long long> answer = getBestPair();
cout<<answer.first<<" "<<answer.second;
return 0;
}이진탐색
#include <iostream>
#include <vector>
#include <cstdlib>
#include <climits>
// boj 2467 용액, 이진탐색, 골드 5
using namespace std;
vector<long long> numbers;
pair<long long, long long> getBestPair(){
pair<long long, long long> answer;
long long best_sum = LLONG_MAX;
for(int i=0; i<numbers.size()-1; i++){
int flag = numbers[i];
int left = i+1, right = numbers.size()-1;
while (left<=right){
int mid = (left+right)/2;
int sum = flag + numbers[mid];
if (best_sum > abs(sum)){
best_sum = abs(sum);
answer.first = numbers[i];
answer.second = numbers[mid];
}
if (sum<0) left = mid+1;
else right = mid-1;
}
}
return answer;
}
int main() {
int N;
cin>>N;
numbers.assign(N, 0);
for (int i = 0; i < N; ++i) cin>>numbers[i];
pair<long long,long long> answer = getBestPair();
cout<<answer.first<<" "<<answer.second;
return 0;
}