BOJ 2470 - 두 용액
“투 포인터 && 이분 탐색”
문제 링크
CODE
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
int N;
int arr[101010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); std::cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++)
cin >> arr[i];
sort(arr+1, arr+N+1);
int start = 1; int end = N;
int first, second;
int mn = 2147483647;
while (start < end)
{
int temp = mn;
int result = abs(arr[start] + arr[end]);
mn = min(result, mn);
if (mn != temp) {
first = arr[start];
second = arr[end];
}
if (arr[start] + arr[end] < 0)
start += 1;
else if (arr[start] + arr[end] == 0)
break ;
else
end -= 1;
}
cout << first << ' ' << second << '\n';
return 0;
}
DESCRIPTION
투 포인터를 사용하는 대중적인 문제이다. 용액의 종류가 100000개까지 들어오기 때문에 for 문을 2번 순회하게 되면 시간 초과가 발생한다.
O(100000 * 100000)따라서 배열을 1회 순회하면서 적절한 값을 찾아내야 한다. 이 문제의 경우 주어진 배열을 오름차순으로 정렬한 후 양 끝값(st, en)을 시작점으로 잡고, 그 합이 0보다 크다면 en을 줄이고 작다면 st을 늘리면서 값을 좁혀나가면서 인덱스를 기록한다. 이렇게 하면 배열을 1회 순회하면서 절댓값이 가장 0에 가까운 두 용액을 찾아낼 수가 있다.
이분 탐색으로도 풀 수 있다. 이분 탐색을 사용한 풀이는 아래와 같다.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;
int N;
int arr[101010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); std::cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++)
cin >> arr[i];
sort(arr+1, arr+N+1);
int first, second;
int mn = 2147483647;
for (int i = 1; i <= N; ++i)
{
int lo = i + 1, hi = N;
while (lo <= hi) // 이분 탐색 적용
{
int mid = (lo + hi) / 2;
int sum = arr[i] + arr[mid];
int result = abs(sum);
if (result < mn)
{
mn = result;
first = arr[i];
second = arr[mid];
}
if (sum < 0)
lo = mid + 1;
else
hi = mid - 1;
}
}
cout << first << ' ' << second << '\n';
return 0;
}
- for 문을 1회 순회하면서, 자신보다 큰 값을 가진 용액들을 이분 탐색하면서 절댓값이 가장 작은 용액을 기록한다. 코드를 잘 보면 알 수 있는데, 이 코드 시간 복잡도가
O(N * logN)이다. for 문을 순회하면서 이분 탐색까지 실행하기 때문이다.
