greentea31's Note

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

풀이 과정

배열에서 두 요소의 합이 x가 되는 경우의 수를 구하는 문제이다.

O(N^2)인 완전 탐색방법으로 풀 수는 있겠지만 배열의 길이가 10만까지 들어오므로 O(N^2)로 처리하면 1초내로 연산이 다 불가능하고 시간 초과가 발생한다.

해결 방법은 크게 2가지가 있다.

1. 투 포인터

배열을 정렬한 뒤, left, right 포인터를 배열의 시작지점, 끝부분에 위치시킨다. 그 후 배열의 left번째 index의 원소 + right번째 index의 원소를 x와 비교한 후, x보다 작으면 left를 전진, 0보다 크면 right를 후진, x와 같으면 left, right를 전진, 후진 시킨 뒤 정답을 1 늘려주면 된다.

2. 배열로 자연수 존재 여부 판단

(x - 배열의 원소) 라는 수가 나온 적이 있는지를 체크하는 배열을 두고, 등장한 적이 있으면 합해서 x가 되므로 답의 개수를 하나씩 늘리면 된다.

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

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

    int x;
    cin >> x;

    sort(a, a+n);

    int left = 0;
    int right = n-1;
    int answer = 0;

    while (left < right) {
        int temp = a[left] + a[right];
        if (temp < x) {
            left++;
        } else if (temp > x) {
            right--;
        } else {
            left++; right--;
            answer++;
        }
    }

    cout << answer;

    return 0;
}

배열

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
bool exist[2000005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

    int x;
    cin >> x;

    int answer = 0;

    for (int i = 0; i < n; i++) {
        if (x-a[i] > 0 && exist[x-a[i]]) answer++; // 나온 적 있으면 정답 증가
        exist[a[i]] = true; // 나왔다고 처리
    }

    cout << answer;

    return 0;
}