[C++] 백준 1253 - 좋다

<문제 링크> 

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

2110번: 공유기 설치

<알고리즘 분류> 

- 이분 탐색 (Binary Search)

- 투 포인터 (Two Pointer)

<풀이>

 투 포인터를 이용하여, 서로 다른 두 수를 지목했고, 이들의 합을 구했다.

 

 시간복잡도의 경우, 

   - N개의 숫자를 모두 순회해야 하므로 O(N)

   - 각각의 숫자들이 서로 다른 두 수의 합으로 구할 수 있는지를 구하는 것은 투 포인터로 구현했으므로 O(N) 

       따라서 O(N*N) = O(N^2)이다.

 

 CheckIf() 함수에서 주목해야 할 점은, 두 수의 합이 되는 숫자를 삭제(erase)해주었는데, 이 이유는 서로 다른 두 수의 합에 자기 자신의 숫자가 포함되면 안되기 때문이다.

아래 예시를 통해 비교를 해보자. 

1. [0 1 2]에서 0 + 2 = 2 는 안 된다. 2가 자기 자신의 숫자이기 때문이다.

 

2. [0 1 2 2] 에서는 0 + 2 = 2가 가능하다. (앞의 2를 쓰면 뒤의 2를 이용하여 0+2해주기, 뒤의 2를 쓰면 앞의 2를 이용하여 0+2해주기 - 총 2가지)

left 와 right는 각각 양 끝의 index를 받는다. (left = 0, right = N-2)

여기서 N-2가 왜 끝index인지는 잘 생각해보자! 

이후에는 while문을 사용하여, left 와 right값을 각각 더해주고 빼주면서, 조건에 맞다면 count++ 를 해주었다.

<코드>

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;

int N; 
vector <int> num;

bool CheckIf(int a, int index){
    num.erase(num.begin() + index);

    int l = 0;
    int r = N-2;

    while(l<r){
        if(num[l]+num[r] == a){
            num.insert(num.begin() + index, a);
            return true;
        }
        else if(num[l]+num[r] < a){
            l++;
        }
        else{
            r--;
        }
            
    }

    num.insert(num.begin() + index, a);
    return false;

}



int main(){
    cin >> N;
    for (int i=0; i<N; i++){
        int x;
        cin >> x;
        num.push_back(x);
    }

    sort(num.begin(), num.end());
    int count =0;

    for (int i=0; i<N; i++){
        if (CheckIf(num[i], i)){
            count ++;
        }
    }

    cout << count;
}