[C++ 백준 풀이][Gold IV] 2473번 : 세 용액 (투 포인터 알고리즘 응용)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 2473번 : '세 용액' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold IV에 해당하며, 이 문제를 풀기 위해 필요한 개념에는 투 포인터 알고리즘이 있씁니다.

 

[C++ 백준 풀이] 1806번 : 부분합 / 2467번 : 용액 (두 포인터 알고리즘)

 

이 문제를 풀기 전에 위의 선행 문제를 풀고 오면 더욱 좋습니다. (2467번 : 용액)

 

 

2473번 : 세 용액

 

문제를 보면 정렬되지 않고 무작위로 주어진 데이터들에 대해, 세 데이터의 합의 절댓값이 0에 가장 가까운 세 데이터를 뽑아 오름차순으로 출력하는 문제입니다.

같은 절댓값의 합이 여러 개인 경우에는 아무거나 출력하면 됩니다.

투 포인터 알고리즘을 사용하면 정렬된 데이터의 양 끝점에서부터 탐색을 하면 되는데, 이렇게 3개의 값을 선택해야 하는 경우에는 어떻게 포인터를 이동시켜야 할지 애매할 수 있습니다.

그러나 이 경우에는 그냥 나머지 하나의 포인터는 앞에서부터 순차적으로 이동하면서 탐색하면 됩니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <algorithm>
#define INF 3000000001
using namespace std;

long long arr[5005] = {0, };
long long Abs(long long a) { return a>=0?a:-a; }

int main() {
    int N, Left, Right;
    long long temp, Min = INF, ans[3];
    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%lld", &arr[i]);
    sort(arr+1, arr+N+1);
    for(int i=1; i<=N-2; i++) {
        Left = i+1, Right = N;
        while(Left < Right) {
            temp = arr[i] + arr[Left] + arr[Right];
            if(Abs(temp) < Min) {
                Min = Abs(temp);
                ans[0] = arr[i], ans[1] = arr[Left], ans[2] = arr[Right];
            }
            if(temp < 0) Left++;
            else Right--;
        }
    }
    printf("%lld %lld %lld", ans[0], ans[1], ans[2]);
}

 

풀이를 보면, 우선 데이터를 정렬해야 투 포인터 알고리즘을 사용할 수 있으므로 sort 함수를 사용해서 오름차순으로 정렬을 해주었습니다.

그 다음 첫 번째 포인터를(arr[i]) i=0부터 N-2까지 이동시키고, 나머지 2개의 포인터로 투 포인터 알고리즘을 이용하였습니다.

즉, Left는 i+1에서, Right는 N에서 시작해서 투 포인터 알고리즘을 수행하는 것입니다.

이렇게 되면 루프가 하나 더 생겨서 시간 초과가 발생할 것이라고 우려할 수 있지만, 투 포인터 알고리즘 자체가 애초에 O(N)에 가깝게 탐색을 수행하기 때문에 시간 초과가 발생하지 않습니다.

 

이 문제에서 또 주의해야 할 점은 세 용액의 합을 계산하는 과정에서 오버플로우가 발생할 수 있으므로, arr 값 자체를 long long 데이터형으로 입력받는 것이 좋습니다.

 

 

풀이 코드를 제출해보면 28ms로 생각보다 짧은 시간 안에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

만약 여기서 문제가 더 심화되어서 4개의 값을 결정해야 한다면, 루프 하나를 더 설정하고 2개는 반복문으로, 2개는 투 포인터 알고리즘으로 수행하거나, (이 경우는 데이터의 범위가 더 작아야 하거나 시간 제한이 더 넉넉해야 할 것입니다.) 아니면 이분 탐색을 수행하는 방법도 생각해볼 수 있을 것입니다.