[투포인터] 두 수의 합(3273)(C++)

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

3273번: 두 수의 합

 

1. 문제 개요

 

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

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

투 포인터를 사용하는 문제를 처음 풀어봤다.

투 포인터는 두 개의 포인터(C언어에서 말하는 포인터가 아니라 배열의 원소 중 한 곳을 가르키는 커서)를 사용해서 배열을 O(N)의 시간으로 탐색하는 알고리즘이다. 

정렬된 배열에서 많이 사용되며 O(n^2)의 연산에서 필요없는 연산을 버려 O(N)의 시간으로 줄인다.

 

N개의 원소 중에 두 개의 합이 M이 되는 쌍의 개수를 찾는 코드는 아래와 같다.

int left = 0, right = N-1, ans = 0;
    
while(left < right) {
     if(v[left] + v[right] > M) right--;
     else if(v[left] + v[right] < M) left++;
     else {
         ans++;
         right--;
      }
}

 

 

4. 전체 코드

 

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

using namespace std;

int main(void) {
    int N,M;
    vector<int> v;
    
    scanf("%d",&N);
    
    int temp;
    for(int i=0;i<N;i++) {
        scanf("%d",&temp);
        v.push_back(temp);
    }
    
    scanf("%d",&M);
    sort(v.begin(), v.end());
    
    int left = 0, right = N-1, ans = 0;
    while(left < right) {
        if(v[left] + v[right] > M) right--;
        else if(v[left] + v[right] < M) left++;
        else {
            ans++;
            right--;
        }
    }
    
    printf("%d",ans);
}