백준 3273번 C++ 풀이

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

3273번: 두 수의 합

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	실버 3

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

---

단순히 브루트포스의 방법으로 두 수의 합을 확인하면 시간초과가 날 것이다. 숫자가 10만개가 들어오기 때문에, 브루트포스로 접근하여 이중 반복문을 돌렸다가는 100억번을 돌고, 이는 1초를 넘어갈 것이 뻔하다. 따라서 이런 경우에 O(n)으로 처리할 수 있는 투포인터 알고리즘으로 접근한다 (C언어의 그 포인터와 어쩌면 유사하겠다).

 

입력받은 수열을 오름차순으로 정렬하고, 포인터 하나는 맨 앞에, 남은 하나는 맨 오른쪽에 위치시킨다. 이후 앞의 포인터는 뒤로, 뒤의 포인터는 앞으로 이동하면서 합이 X가 되는 경우를 모두 세면 된다. 이동 횟수가 배열의 길이와 같기 때문에, 이 알고리즘은 O(n)이 되기 때문에 제한 시간안에 끝낼 수 있다.

 

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

int n, target;
vector<int> v;

void input() {
    cin >> n;
    v.resize(n);
    for(int& x : v) cin >> x;
    cin >> target;
    sort(v.begin(), v.end());
}

void sol() {
    int cnt = 0, sum = 0, lo = 0, hi = n - 1;
    while(lo < hi) {
        sum = v[lo] + v[hi];
        if (sum > target) hi--;
        else if (sum < target) lo++;
        else {
            cnt++;
            hi--;
            lo++;
        }
    }
    cout << cnt;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}