둘이 뭔가가 다르긴 했는데 지금은 기억이 잘 안 난다.
근데 아무튼 중요한 건 사실상 같은 문제라 하나 풀고도 두 문제를 맞춘 것과 같은 효과를 낼 수 있다는 것(!)
그것도 심지어 골드 5(!!!)
완전히 남는 장사일 수 밖에 없다.
풀이 자체는 간단히 투 포인터를 이용해서 할 수 있다.
먼저 모든 원소를 소트한 뒤, 맨 왼쪽과 오른쪽에 포인터를 세팅해둔다. 그러면서 한 칸 한 칸씩 포인터를 옮기면서 두 포인터가 가리키고 있는 원소들의 합을 구하는 것이다. 만약 그 합이 0보다 크다면, 양수의 크기를 줄여야 하므로 오른쪽 포인터를 이동시키고, 반대라면 음수의 크기를 키워야 하므로 왼쪽 포인터를 이동시킨다. (이것이 가능한 것은 앞에서 원소를 소트해뒀기 때문이다. 만약 정렬되어 있지 않다면 이 방법을 사용할 수 없다.
이 과정을 반복하면서 합을 계산하고, 그 합이 만약 0과 가장 가까웠던 값보다 더 가깝다면 최소값을 갱신하고, 해당 원소를 저장한다. 이 과정을 두 포인터가 교차될 때까지 반복한다.
정답을 얻은 코드는 다음과 같다.
//두 용액 - 골드 5
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int a_l, a_r, min_char = 2*1e9;
void findMin(const vector<int>& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int sum = arr[l] + arr[r];
if (abs(min_char) > abs(sum)) {
min_char = sum;
a_l = arr[l];
a_r = arr[r];
}
if (sum > 0) {
r--;
} else {
l++;
}
}
}
int main() {
int n;
vector<int> arr;
cin >> n;
arr.assign(n, 0);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort (arr.begin(), arr.end());
findMin(arr);
cout << a_l << ' ' << a_r;
}
이거랑은 별개로, 같은 문제인데 이번에는 용액 3개를 가지고 푸는 버전도 존재한다.
세 용액
아무래도 이 문서가 도움이 될 것 같다.
triplet sum
보면 세 가지 방법을 알려주는데, 하나는 브루트포싱이라 뭐... 의미가 없고, 하나는 투 포인터, 마지막은 해싱이다.
투 포인터 방법도 근데 뭐 크게 다른 건 없는 게, 왼쪽에 원소를 하나 고정해 둔 다음에 그 오른쪽 원소들을 위에서 투 포인터로 푼 것처럼 옮겨가면서 가운데에서 만날 때까지 하고, 그 다음 왼쪽 원소를 한 칸 오른쪽으로 옮겨서 또 하고, 또 왼쪽 원소를 오른쪽으로 옮기고... 의 반복이다. 원소가 n개라고 할 때, 왼쪽 원소를 옮기는 게 O(N)이고, 또 포인터 연산이 O(N) 걸리니까 시간복잡도는 O(N^2)가 될 것이다. 그래도 다항식 시간으로 끊기니까 다행인가...
세 번째 방법은 엄밀히 말하면 위 문제를 푸는 데 사용할 만한 방법은 아니고, 그냥 뭐... 위랑 대단하게 다를 건 없다. 차이라면 뭐 원소 찾느라 set 쓴다? 근데 이것도 이 문제에서는 0이 되는 케이스를 찾는 게 아니라 0이랑 가까운 케이스를 찾는 거라서... 일일히 또 탐색하면 n^3 되니까 걍 투 포인터 변형으로 푸는 게 나을 것 같다.
아무튼 그렇다. 이 문제도 한 번쯤 풀어봐야겠다. 대신 인풋 범위 보니까 2개까지는 21억 안 넘는데 3개부터는 넘을 수 있으니까 자료형 좀 주의하고.