[Algorithm] Baekjoon 1253번 : 좋다

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
vector<int> v;
unordered_map<int, bool> m;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    v.resize(n);
    for (int i = 0; i < n; ++i)
    { 
        cin >> v[i];
    }
 
    int answer = 0;
    sort(v.begin(), v.end());
 
    for (int i = 0; i < n; ++i)
    {
        int targetNum = v[i];
 
        int leftIndex = 0;
        if (i == 0) ++leftIndex;
 
        int rightIndex = n - 1;
        if (i == n - 1) --rightIndex;
 
        while (leftIndex < rightIndex)
        {
            int curNum = v[leftIndex] + v[rightIndex];
            
            if (curNum == targetNum)
            {
                ++answer;
                break;
            }
 
            if (curNum < targetNum) // 숫자가 모자르면
            {
                ++leftIndex;
                if (leftIndex == i) ++leftIndex;
            }
            else // 숫자가 초과되면
            {
                --rightIndex;
                if (rightIndex == i) --rightIndex;
            }
        }
    }
 
    cout << answer;
}
 
 
 

 

주어진 숫자들 중, 특정조건을 만족하는 수의 개수를 구하는 문제이다.

특정조건이란 '자신을 제외한' 나머지 두 수를 합쳤을 때, 자신과 같아진다면 자신은 특정조건을 만족하게된다.

 

결국 '자신'이라는 특정수를 만족하기위한 두 수를 구하는것이니, 투포인터를 활용할 수 있다.

오름차순을 한 다음, 양쪽에 투포인터를 두고 로직을 수행한다.

투포인터의 값을 합친게 특정수보다 작다면, 값을 올려줘야하니 ++leftIndex를 하고 반대의 경우에는 --rightIndex를 해준다.

 

주의해야할 점은, '자신을 제외한' 두 수의 합이기 때문에 만약 포인터를 움직여주는 과정에서 자신에 해당하는 인덱스를 만났을 경우, 한번 더 움직여줘야 한다.

투포인터의 시간복잡도는 O(N)이며, 투포인터로직을 최대 n번만큼 수행하기 때문에 이 문제에서의 시간복잡도는 O(n^2)가 된다.

 

n값은 최대 2천이니, n^2이여도 최대 4,000,000 으로 무난히 통과할 수 있따.