투 포인터를 이용한 문제이다. 이 문제에서는 세가지 용액의 값을 구해야하므로 세가지의 위치를 구해야한다. 반복문을 돌면서 i
를 기준으로 투 포인터를 이용해주었다. 먼저 입력받은 값을 오름차순으로 정렬을 해주고, i
를 고정으로 두고 i + 1
과 끝의 값을 기준으로 투 포인터를 시작하여 합의 절대값을 구해 비교하며 절대값이 가장 작은 세가지 인덱스를 구해 출력해주었다.
처음에는 처음과 끝 값을 고정으로 하고 가운데 값을 이동하며 찾는 방식으로 구현을 했었는데 어딘가 잘못됬는지 계속 틀렸습니다가 나왔었다. 아마도 투 포인터 안에서 반복문을 돌다보니 모든 값을 탐색하지 못했던 것 같다. 반복문 안에서 투 포인터를 돌도록 바꾸었더니 통과를 하였다. 생각보다 시간이 오래 걸린 문제였다. 투 포인터를 활용하는 방식에 대해 잘 알아두어야 겠다.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
long long A[5000];
void solution() {
sort(A, A + N);
int a, b, c;
long long sum = 3000000000;
for (int i = 0; i < N - 2; i++) {
int start = i + 1, end = N - 1;
while (start < end) {
long long tmp = A[i] + A[start] + A[end];
if (sum > abs(tmp)) {
a = i;
b = start;
c = end;
sum = abs(tmp);
}
if (tmp < 0) start++;
else end--;
}
}
cout << A[a] << " " << A[b] << " " << A[c];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
solution();
return 0;
}