2024 - 01- 20 C++ 코딩테스트 10주완성 D+68

백준 3273 문제 - 두 수의 합

 

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)

 

출력

 

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

 

 

#include<bits/stdc++.h>

using namespace std;

int l,r,n,x,ret;

int main()
{
    cin >> n;
    vector<int> a(n);

    for(int i =0; i < n; i++) cin >> a[i];

    cin >> x;
    sort(a.begin(),a.end());
    l = 0, r = n - 1;
    while(l < r)
    {
        if(a[l] + a[r] == x) r--,ret++;
        else if(a[l] + a[r] > x) r--;
        else if(a[l] + a[r] < x) l++;
    }

    cout << ret;
}

 

더해서 X가 나오는 쌍을 주어진 집합 전부 이중반복문을 돌려 계산하면

 

1 ≤ n ≤ 100000 범위이므로 1,000,000 X 1,000,000 은 1억을 가뿐히 넘으므로 시간초과가 난다!

 

그래서 이용하는 것이 투포인터이다.

 

왼쪽부터 탐색하는 포인터와 오른쪽부터 탐색하는 포인터 두개를 이용하는 것이다.

 

입력받은 집합을 오름차순으로 정렬시켜준뒤,

 

투 포인터가 가르치는 원소의 합이 x보다 클 시, 오른쪽 포인터를 이동시켜 좀더 작은 수로 이동시켜주고

 

x보다 작을 시, 왼쪽 포인터를 이동시켜 좀더 큰 수로 이동시켜준다.

 

그리고 x가 나올시, 쌍의 개수를 저장하는 ret++를 시켜주고 오른쪽 포인터를 감소시켜준다.