백준 2470번 : 두 용액 - 투포인터

https://www.acmicpc.net/problem/2470

2470번: 두 용액

1. 문제설명

두 용액의 합이 가장 0에 가까울 때의 두 용액의 값을 출력하는 문제이다.

 

단순하게 나올 수 있는 모든 용액의 합을 구하면 시간복잡도가 O(N^2)이 되기 때문에 틀린다.

 

우선 모든 용액의 값을 받아 정렬하고

가장 작은값과 가장 큰값을 start 지점과 end지점으로 두어서 더해본다.

 

v[start] + v[end] > 0 이라면 두 용액의 합이 0에 가까워지기 위해서

두용액의 합을 줄여야한다.

 

이 때 이미 모든 용액은 오름차순으로 정렬되어 있기 때문에 두 용액의 합을 줄이기 위해서는

end의 값을 줄여야한다

 

반대로 v[start] + v[end] < 0 일 때는 두 용액의 합이 0에 가까워지기 위해

두 용액의 합을 키워야하므로

start의 값을 키워야한다.

 

이 과정을 start < end 인 동안 반복한다.

두 용액은 다른 용액을 사용해야 하기 때문에 start==end가 되어서는 안된다.

 

이 과정을 반복하면 abs(v[start] + v[end])가 최소가 되는 지점을 찾을 수 있다.

이를 코드로 옮기면 된다.

 

 

정렬할 때 시간복잡도 O(NlogN)

start, end를 찾는 과정 O(N) 이므로

O(NlogN)으로 이 문제를 해결 할 수 있다.

 

 

---

2.문제풀이코드

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> v;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++){
        int num;
        cin >> num;
        v.push_back(num);
    }

    sort(v.begin(), v.end());


    int st = 0, en = n-1;

    int ans_val = INT_MAX;

    int ans1, ans2;
    while(st < en){
        int sum = v[st] + v[en];
        if(sum==0) {
            cout << v[st] << ' ' << v[en];
            return 0;
        }

        if(ans_val >= abs(sum)){
            ans_val = abs(sum);
            ans1 = v[st];
            ans2 = v[en];
        }

        //두합이 0보다 크다면 en의 값을 줄여야하고 0보다 작다면 st의 값을 증가시킨다.
        if(sum > 0){
            en--;
        }
        else{
            st++;
        }
    }

    cout << ans1 << ' ' << ans2;


    return 0;
}

백준 2470번