c++ 백준 3273 두 수의 합

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

문제 입력을 보면 1 ≤ n ≤ 100000=10^5이고, 시간 제한이 1초이다. 따라서 2중 for문을 수행하면 10^10으로 1초에 수행할 수 있는 연산인 3~5억번을 넘게 되므로 시간 초과가 발생한다. 따라서 이 문제는 O(n)으로 풀이를 해야한다.

처음 2중 for문 풀이

#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, x;
    int a[100000];
    cin >> n;
    for(int i=0; i<n; i++)  cin >> a[i];
    cin >> x;

    int cnt=0;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            if(a[i]+a[j] == x) {
                cnt++;
                break;
            }
        }
    }
    cout << cnt;

모든 경우의 수를 확인하면서 cnt를 증가시켰다. 시간 복잡도는 O(n^2)으로 시간초과가 발생한다.

두 번째로 다른 방법으로 풀이 해보았는데 이것도 틀린 풀이이다.

#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, x;
    int a[100000];
    cin >> n;
    for(int i=0; i<n; i++)  cin >> a[i];
    cin >> x;

    int cnt=0;
    for(int i=0; i<n; i++) {
        if(find(a+i+1, a+n, x-a[i]) != a+n) {
            cnt++;
        }
    }
    cout << cnt;
}

find는 시간 복잡도가 O(1)이 아니라 O(n)이기 때문에 마찬가지로 전체 시간 복잡도는 O(n^2)이 된다.

맞은 풀이

#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, x;
    int a[1000000];
    bool occur[2000000] = {};
    cin >> n;
    for(int i=0; i<n; i++)  cin >> a[i];
    cin >> x;

    int cnt=0;
    for(int i=0; i<n; i++) {
        if(x-a[i]>0 && occur[x-a[i]]) { // x-a[i]가 유효한 원소인지 검사
            cnt++;
        }
        occur[a[i]] = true;
    }
    cout << cnt;
}

앞의 [자료구조]0X03배열의 연습문제 풀이와 같은 방식으로 O(n)으로 해결할 수 있다.