배열

“0x03강 - 배열”

[바킹독 실전 알고리즘] 0x03강 - 배열

워크북 : 백준 10808, 2577, 1475, 3273

백준 3273, 두 수의 합


내코도

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <utility>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;

int arr[2000002] = {0, };
int n; // 1<=n<=100000
int x; // 1<=x<=2000000
int res;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n; // 9;

    int keys[n];
    fill (keys, keys + n, 0);

    for (int i = 0; i < n; i++) {
        cin >> keys[i];
    }

    cin >> x;

    for (int i = 0; i < n; i++) {
        if (x > keys[i]) {
            if (arr[x - keys[i]]) 
                res++;
        }
        arr[keys[i]]++;
    }
    cout << res << endl;
    return 0;
}

  • 배열 내에서 합이 13이 되는 두 수를 찾기 위해서 배열을 순회할 때, 예를 들어 예제로 주어진 배열의 5에서는, 8을 확인한다. 해당 수의 짝이 되는(합이 13이 되는) 다른 인덱스의 수를 확인하는 방법은 숙지해두는게 좋은 것 같다. (메모의 “두 포인터”가 이 기술의 대략적인 명칭같다).

  • 짝을 확인하기 위해서, 합인 x에 해당 수인 keys[i]를 빼는데 이때 x - keys[i]가 음수일 경우, outofBound에러가 발생하기 때문에 x < keys[i]인 경우, 두 포인터를 체크할 수가 없다. 즉 합이 13인 수를 찾는데 14가 들어오면, 애초에 합이 13이 될 수가 없기 때문에 이런 수들은 짝 포인터를 확인하지 않고 그냥 넘어간다.