[Baekjoon] 3273 - 두 수의 합 (C++)

> 문제

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

3273번: 두 수의 합

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

---

> 풀이

idea 1) memorization

1. 길이가 k+1인 배열을 만들고 (memory[x+1], memory[x]에 쌍 개수 저장할 것)
2. 입력받은 숫자들을 하나씩 순회하며 (arr[0]~ arr[n-1])
3. 만약 memory[]의 그 숫자에 해당하는 칸이 존재한다면 (memory[arr[i]]) 1을 집어넣는다.
4. 그리고 memory[x - arr[i]] 에 1이 담겨 있다면, 쌍이 존재한다는 의미이므로 memory[x]의 값을 1 증가시킨다.
5. memory[x]의 값을 출력한다.

이처럼 길이가 x+1인 배열을 만들고, 두 수의 합으로 x를 만들 수 있는 쌍이 ai, aj가 다르면 유일하다는 점을 이용해 memory에 각각 x를 구성하는 ai - aj가 존재함을 저장해 ai마다 x를 만들 수 있는 aj가 있는지 확인하는 방법으로 문제를 해결할 수 있다.

// Baekjoon No. 3273 두 수의 합
// Time Complexity O(n)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    int i;
    cin >> n;
    vector<int> arr(n);
    for (i = 0; i < n; i++)
        cin >> arr[i];
    cin >> x;
    vector<int> memory(x + 1, 0);

    // solving
    for (i = 0; i < n; i++) {
        if(arr[i] < x)
            memory[arr[i]] = 1;
        if (x - arr[i] > 0 && arr[i] * 2 != x && memory[x - arr[i]])
            memory[x] ++;
    }
    cout << memory[x];

    return 0;
}

idea 2) 투 포인터

그리고 문제 유형에 적혀 있는 투 포인터 방식을 이용하는 방법이 있다.

1. 쌍 개수를 저장할 cnt 변수를 0으로 초기화한다.
2. 배열 arr[]에 ai 값들을 입력받는다.
3. arr[]을 오름차순 정렬한다. (시간복잡도 O(nlogn)
4. 정렬한 arr에서 arr[0]이 arr[n-1]이랑 더했을 때 x보다 큰지 작은지 확인한다.
5. 만약 그 값이 x보다 크다면, arr[0] + arr[n - 1 - i] 가 x보다 작거나 같을 때까지 i를 0부터 증가시킨다. (arr의 오른쪽 idx--)
6. 만약 그 값이 x와 같다면, cnt++, arr의 오른쪽 idx -- (또는 왼쪽 idx ++)
7. 만약 그 값이 x보다 작다면, arr의 왼쪽 idx ++
8. 이대로 arr의 오른쪽 idx와 왼쪽 idx가 겹칠 때까지 반복을 수행한다.

언뜻 보면 arr[l] (왼쪽 idx)를 증가시켰을 때 arr[r]과의 합이 x보다 커버리는 경우가 생길 수도 있다고 생각할 수 있지만, 애초에 arr[l]을 증가시키는 경우는 arr[l] + arr[r] < x인 경우이므로 이 경우에는 r--을 해주어야 한다.

 

> 결론

- 투 포인터를 이용하면 O(nlogn), memorization을 이용하면 O(n)

- 배열을 다룰 때 idx 범위를 조심할 것 (memorization에서 0 < arr[i] < x, 2*arr[i] != x)