백준 1940 주몽

세 가지 풀이로 문제를 해결해보았다.

n <= 15,000이라는 조건을 보고 O(n^2)풀이도 통과하겠다 싶어 bruteforce로 먼저 풀었다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    int cnt = 0;
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (v[i] + v[j] == m) cnt++;
        }
    }
    cout << cnt;
}

92ms로 통과했다.

근데 너무 쉽게 통과해서 뭔가 더 빠른 풀이가 없을까 생각해보았다.
1. 우선 정렬을 떠올렸다.
2. 하나의 숫자를 a라고 하면 다른 숫자는 m - a이다.
3. 그럼 모든 숫자에 대해, 나머지 다른 숫자를 이분탐색으로 찾으면 O(nlogn)에 해결이 가능했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    int cnt = 0;
    sort(v.begin(), v.end());
    for (int i = 0; i < n-1; ++i) {
        int target = m - v[i];
        if (binary_search(v.begin()+i+1, v.end(), target)) cnt++;
    }
    cout << cnt;
}

정렬을 하는 과정에서 왠지 투 포인터로도 풀릴 것 같았다. 그래서 시도해보았다.
1. 이분탐색 풀이처럼 일단 정렬을 한다.
2. 수열의 양 끝에 포인터를 놓고(a, b) 포인터가 가리키는 숫자의 합이 작을 경우 a++, 클 경우 b--, 같을 경우 cnt++을 해주고 고유한 숫자이기 때문에 a++와 b--를 동시에 해주었다.
전체 시간복잡도는 이분탐색과 같은 O(nlogn) (정렬)이 지배하지만 실제 탐색을 수행하는 과정에서 이분탐색은 O(nlogn), 투 포인터는 O(n)이기 때문에 투 포인터가 약간 빠르다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    int cnt = 0;
    sort(v.begin(), v.end());
    int a = 0;
    int b = n-1;
    while (a < b) {
        if (v[a] + v[b] < m) {
            a++;
        } else if (v[a] + v[b] > m) {
            b--;
        } else {
            cnt++;
            a++;
            b--;
        }
    }
    cout << cnt;
}