[백준][C++] 3273번 두 수의 합

두 수의 합

문제 링크

두 수의 합

분석

수열에서 두 수의 합이 특정 수가 되는 쌍을 찾아 쌍의 개수를 구하는 문제입니다.

수열에는 최대 10만 개의 정수가 중복 되지 않고, 양수로만 값이 주어집니다.

문제에서 1 ≤ i < j ≤ n 는 같은 인덱스를 사용하지 않아야하고, 중복 쌍을 제거한다는 의미입니다.
예를 들어, (0, 1)이라는 쌍이 있을 때 (1, 0)이라는 쌍은 결과 값에 포함시키지 않아야 합니다.

우선 특정 수로 쌍을 구하고자 할 때 수열에 무작위 값으로 $x$에 뺄셈을 할 경우 $x$를 만들기 위한 값을 구할 수 있다는 것을 알아야합니다.
식으로 나타낸다면 수열에서 덧셈으로 $x$를 만들기 위한 값을 $a$와 $b$라고 했을 때, $b = x - a$가 됩니다.

이 문제를 풀 수 있는 방법은 다음과 같습니다.

1. HashSet을 사용하는 방법
   • $x - a$를 할 때 $b$가 존재하는지 $O(1)$에 확인 가능
2. 정렬 후 투 포인터를 사용하는 방법
   • 해당 문제에서 가장 많이 쓰이며 정석적인 방법
3. 정렬 후 이분 탐색을 하는 방법
   • 복잡하며, 시간 복잡도 등 이점이 거의 없다.
4. 카운팅 배열을 활용하는 방법
   • 카운팅 배열 자체의 공간 복잡도가 최대 10만이지만 상수로 취급 가능

브루트포스의 경우 시간초과가 발생하여 좋지 않은 방법입니다.

풀이

#include <iostream>
#include <vector>
#include <unordered_set>

int main()
{
    // 수열의 크기를 입력 받는다.
    int NumberCount;
    std::cin >> NumberCount;

    // 수열을 배열로 관리한다.
    std::vector<int> NumArr;
    for (int i = 0; i < NumberCount; ++i)
    {
        int Number;
        std::cin >> Number;

        NumArr.push_back(Number);
    }

    // 목표 합을 입력 받는다.
    int TargetNumber;
    std::cin >> TargetNumber;

    // 계산하며 등장한 숫자를 저장한다.
    std::unordered_set<int> FoundNumber;
    int FoundCount = 0;

    // 수열을 순회한다.
    for (int i = 0; i < NumArr.size(); ++i)
    {
        // a와 더해서 x를 만들 값을 구한다.
        int b = TargetNumber - NumArr[i];

        // 이미 이전에 b가 존재할 경우 쌍이 존재한다.
        // 이전 값만 확인해서 (a, b)와 (b, a)를 중복으로 세지 않는다.
        if (FoundNumber.count(b))
        {
            ++FoundCount;
        }

        // 현재 값 a를 저장한다.
        // 이후에 나오는 값과 쌍을 이루는지 확인하기 위함이다.
        FoundNumber.insert(NumArr[i]);
    }

    std::cout << FoundCount;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 정수를 입력받는 반복문 $O(n)$
• 정수를 순회하는 반복문 $O(n)$
• $O(n) + O(n) = O(2n)$

공간 복잡도는 $O(n)$입니다.

• 정수를 입력받는 vector $O(n)$
• 쌍을 찾으려는 unordered_set $O(n)$
• $O(n) + O(n) = O(2n)$

메모리: 7108 KB

시간: 52 ms