문제 해석
예제와 함께 설명하자면,
5
-99 -2 -1 4 98
입력할 전체 용액의 수 N을 입력받고, N개 용액의 특성값을 차례로 입력한다.
그 중 두 용액을 섞어 얻는 혼합 용액의 특성값은 그 두 용액의 특성값의 합인데,
예를 들어 -99와 98 용액을 혼합하여 특성값이 -1인 용액을 만들 수 있다.
결론은 이 용액들 중에서 특성값이 가장 0에 가까운(절대값이 가장 작은) 혼합 용액을 만들 수 있는 용액의 쌍을 구하면 되는 문제이다. 따라서 출력은 다음과 같다.
-99 98
그런데 아래와 같이 0에 가까운 특성값을 만들어내는 쌍이 {-100, 103}, {-2, -1} 두 가지일 때는,
4
-100 -2 -1 103
둘 중 아무거나 출력하여도 상관없다.
-100 103
뭐가 필요할까
우선 위에서 언급하였듯 특성값이 가장 0에 가까운 것은 절대값이 가장 작은 것으로 바꿔 말할 수 있고,
어떤 수의 절대값을 출력하기 위해서는 abs 함수를 사용하면 된다.
cout << abs(-1); // 1을 출력!C++에서 abs 함수는 <cmath> 라이브러리를 include 하여 사용할 수 있다.
또한 이 문제에서 가장 중요한 것이 바로 투 포인터라고 할 수 있는데,
이분탐색과 비슷하게도 정렬된 배열에서 어떠한 값을 찾기 위해 사용된다.
배열에서의 양 끝 인덱스를 left와 right으로 잡고 특정한 조건 하에 서로를 향해 이동하다가,
left와 right이 서로 교차할 때 탐색을 끝낸다.
그래서 어떻게 했는데
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
vector<int> v;
int minval = 2000000000;
pair<int, int> min_pair;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
v.resize(N);
for (int i = 0; i < N; i++)
{
cin >> v[i];
}
sort(v.begin(), v.end());
int begin = 0;
int end = N - 1;
while (begin < end) { // 투 포인터 -> 교차될 때 까지
int val = v[begin] + v[end]; // 양 끝 특성값의 합
if (minval > abs(val)) { // 혼합 특성값의 최소값 갱신
minval = abs(val);
min_pair = make_pair(v[begin], v[end]);
}
if (val < 0) {
begin++;
// 음수가 더 커서 혼합 특성값이 음수라면
// 그 절대값을 낮추기 위해서는 음수의 절대값을 낮춤
}
else end--; // 아니면 양수의 절대값을 낮춤
}
cout << min_pair.first << " " << min_pair.second << "\n";
return 0;
}우선 전역변수로 N, 용액의 특성값을 담을 벡터 v를 선언했다.
minval과 min_pair는 코드가 끝날 때엔 혼합 특성값의 절대값의 최소값과, 이를 만드는 쌍이 저장된다.
용액의 특성값이 -10억 ~ +10억 사이기 때문에 혼합 특성값의 절대값은 최대 199999999를 가진다.
따라서 minval의 초기 값을 20억으로 설정하였다.
그런데 이건 아래의 다른 풀이에서 언급하겠지만 minval을 전역이 아니라 main함수 내에서 선언하고,
그 초기값을 abs(v[begin] + v[end]) 로 설정하는 것이 더 나을 수도 있다.
어쨌거나 N과 용액의 특성값을 쭉 입력받고, 용액을 sort 함수로 정렬한다.
begin과 end는 배열의 양 끝이며, while (begin < end) 에서 볼 수 있듯 begin과 end가 만날 때 반복문이 끝이 난다.
val 변수는 현재 while 루프에서 양 끝 특성값의 합이다. 이 변수는 절대값이 아니에용!
이후 if 문에서 val의 절대값이 minval보다 작다면 minval의 값을 갱신해 주고, 그 쌍을 pair로 갱신한다.
그리고 begin과 end가 서로를 향해 땡겨가는 조건이 중요하다고 볼 수 있는데,
혼합 특성값 val이 음수라는 것은 그 절대값을 낮추기 위해선 낮은 쪽의 절대값을 줄여야 하고,
반대로 양수일 때는 높은 쪽의 절대값을 줄이면 val의 절대값이 줄어들게 된다.
위와 같은 특성값이 주어졌다 할 때, val이 음수를 가지므로 begin을 당겨오면 val의 절대값이 줄어든다.
최종적으로 begin과 end가 만나서 while 루프가 끝났을 때엔,
minval 에는 혼합 용액의 최소 절대값이, min_pair에는 그 쌍이 들어있게 된다.
따라서 마지막엔 min_pair의 원소만 출력해주면 끝!
또 다른 방법
다른 코드이지만 사실 맥락은 같다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
vector<int> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
v.resize(N);
for (int i = 0; i < N; i++)
{
cin >> v[i];
}
sort(v.begin(), v.end());
int begin = 0;
int end = N - 1;
int minval = abs(v[begin] + v[end]);
int pair_begin = v[begin];
int pair_end = v[end];
while (begin < end) { // 투 포인터 -> 교차될 때 까지
int val = v[begin] + v[end]; // 양 끝 특성값의 합
if (minval > abs(val)) { // 혼합 특성값의 최소값 갱신
minval = abs(val);
pair_begin = v[begin];
pair_end = v[end];
}
if (val < 0) {
begin++;
// 음수가 더 커서 혼합 특성값이 음수라면
// 그 절대값을 낮추기 위해서는 음수의 절대값을 낮춤
}
else end--; // 아니면 양수의 절대값을 낮춤
}
cout << pair_begin << " " << pair_end << "\n";
return 0;
}위의 코드와 다른 점으로는,
minval의 초기값을 20억으로 설정하지 않고 begin, end 특성값의 합으로 설정한 점,
minval을 갱신한 두 용액의 특성값을 pair 형식으로 저장하지 않고, 따로 변수 두개를 만들어 갱신한 점 뿐이다.
결론은... 두 번째 풀이가 더 짧은 시간인 16ms가 걸렸다!
