[백준] 2470번 : 두 용액

문제

 

---

풀이

 

이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다.

그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다.

 

투 포인터 알고리즘을 사용하기 위해 배열을 정렬한다.

투 포인터라는 뜻은 포인터를 2개 사용한단 것이다.

포인터들은 양쪽에서 출발할 때도 있고 한쪽에서 출발할 때도 있는데 이 문제는 양쪽에서 출발할거다.

 

양 포인터가 가리키는 값들을 합하면 -1이 나온다.

일단 이게 -1과 가장 가까우니까 저 두 조합을 저장해두고...

 

-1은 0보다 작으니까 두 수의 합이 커져야 한다는 뜻이다.

오름차순 정렬이기 때문에 빨간 포인터를 오른쪽으로 옮기면 합이 커지고, 파란 포인터를 왼쪽으로 옮기면 합이 작아질 것이다. 그러니 빨간 포인터를 오른쪽으로 옮겨보자.

 

합이 96이 됐다. 현재의 최소 차이는 1이니까 차이값이 갱신될 일은 없고...

0보다 값이 커졌으니 파란 포인터를 옮겨야겠다.

 

합이 2가 됐고, 차이값은 갱신되지 않고, 합이 0보다 크니 또 파란 포인터를 옮기면

 

-3이 됐고 규칙에 따라 빨간 포인터를 옮기면

 

두 포인터가 만나버린다.

 

이 상황에선 어떤 포인터를 옮겨도 두 포인터의 관계가 역전된다.

그렇기 때문에 두 포인터가 만날때까지만 반복문을 돌면 된다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

vector<int> arr;

pair<int, int> findPair() {
    pair<int, int> result;
    int min_diff = 2 * 1e9 + 1;
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) { //둘의 위치가 역전되면 break
        int sum = arr[left] + arr[right];
        if (sum == 0) { //0이면 바로 리턴
            result = make_pair(arr[left], arr[right]);
            return result;
        } else { //0이 아닐 때
            if (abs(sum) < min_diff) { //최소 차이 갱신 가능한지 확인
                result = make_pair(arr[left], arr[right]);
                min_diff = abs(sum);
            }
            if (sum > 0) //0보다 크면 right 감소
                right--;
            else //0보다 작으면 left 증가
                left++;
        }
    }
    return result;
}

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

    int N;
    cin >> N;
    arr.assign(N, 0);
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    sort(arr.begin(), arr.end());
    pair<int, int> p = findPair();
    cout << p.first << ' ' << p.second;
}

전체 소스코드다.

 

pair<int, int> findPair() {
    pair<int, int> result;
    int min_diff = 2 * 1e9 + 1;
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) { //둘의 위치가 역전되면 break
        int sum = arr[left] + arr[right];
        if (sum == 0) { //0이면 바로 리턴
            result = make_pair(arr[left], arr[right]);
            return result;
        } else { //0이 아닐 때
            if (abs(sum) < min_diff) { //최소 차이 갱신 가능한지 확인
                result = make_pair(arr[left], arr[right]);
                min_diff = abs(sum);
            }
            if (sum > 0) //0보다 크면 right 감소
                right--;
            else //0보다 작으면 left 증가
                left++;
        }
    }
    return result;
}

arr 배열은 main에서 정렬해뒀고 이 함수만 보자.

 

        int sum = arr[left] + arr[right];
        if (sum == 0) { //0이면 바로 리턴
            result = make_pair(arr[left], arr[right]);
            return result;
        }

만약 둘의 합이 0이면 더 볼 것도 없이 리턴한다.

 

        else { //0이 아닐 때
            if (abs(sum) < min_diff) { //최소 차이 갱신 가능한지 확인
                result = make_pair(arr[left], arr[right]);
                min_diff = abs(sum);
            }
            if (sum > 0) //0보다 크면 right 감소
                right--;
            else //0보다 작으면 left 증가
                left++;
        }

0이 아니라면 일단 둘의 합이 지금까지의 합들 중에서 0과 가장 가까웠는지 확인하고

0보다 큰 경우엔 오른쪽 포인터를 조작하고, 작은 경우엔 왼쪽 포인터를 조작한다.