[C++] BOJ 3273번: 두 수의 합

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다.

 

문제의 난이도는 실버 3으로, 투 포인터를 활용하여 푸는 것을 권장받은 문제이다.

 

필자는 투 포인터 방식과 Hash Map을 활용한 방식, 두 가지로 풀어보았으므로 두 가지 모두 서술하도록 하겠다.

문제 링크

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

문제 분석

서로 다른 양의 정수 중 두 개를 골랐을 때, 두 수의 합이 x가 되도록 하는 조합의 수를 구하는 문제이다. 해당 문제는 기본적으로 투 포인터 문제로 분류되어 있다.

문제 풀이

이 문제의 핵심 키워드는 'n개의 서로 다른 양의 정수', '두 수의 합'이다.

1. 투 포인터

 먼저 투 포인터 방식으로 푼 것에 대해 설명하기 전에 투 포인터가 무엇인지부터 작성하겠다. 투 포인터란, 두 개의 점의 위치를 기록하며 배열에 접근하는 알고리즘이다. 시작점과 끝점을 나누어 특정 기준에 따라 점의 위치를 이동하는 방식으로 구현된다. 정렬된 배열을 기준으로 쓰일 때가 많으며, 반복문을 돌 때 시작점과 끝점이 N번 이상 움직여야 반복문이 끝나므로 빅오 표기법으로 O(N)만큼 시간이 걸리게 된다.

 

 이 문제에서는 투 포인터를 사용하기 적합하도록 하기 위해 수열을 한 번 정렬하고, 투 포인터 방식을 사용해 문제를 해결하였다.

 

 투 포인터를 적용할 때에 start, end 두 가지 변수를 두었다. 먼저 end를 start와 같은 배열의 시작점으로 두고 문제를 풀어보았으나 문제가 해결되지 않아 end를 배열의 끝점으로 두고 문제를 해결하였다.

 만약 start와 end를 배열의 시작점으로 두고 문제를 풀면, start와 end가 단방향으로 이동하지 못하는 문제가 발생하여 end를 배열의 끝점으로 두고 풀어야 했다.

 

 투 포인터 방식을 적용해 푼 문제의 코드는 아래와 같다.

int start = 0;
int end = n - 1;
int cnt = 0;

while (start < end)
{
    if (v[start] + v[end] == x)
    {
        cnt++;
        end--;
    }
    else if (v[start] + v[end] > x)
        end--;
    else
        start++;
}

 위 코드에서 cnt는 문제의 조건을 만족하는 쌍의 갯수를 표현한 변수이다.

2. Hash Map

 Hash Map을 통해 문제를 풀 때에는 배열을 정렬하지 않고도 해결할 수 있다. 두 수의 합을 구하는 문제이므로, 두 수를 a와 b라고 한다면 b = x - a이므로 a와 x - a가 존재하는지 확인하면 문제가 해결된다. 여기 작성한 로직을 코드로 구현하면 다음과 같다.

for (int i = 0; i < n; i++)
{
    m[v[i]] = true;
    if (m[x - v[i]] == true && (x - v[i] != v[i]))
        cnt++;
}

 위 코드에서 Hash Map의 변수명은 m으로 작성하였다. 한 번 탐색한 숫자에 대해서는 m에서 true를 갖도록 만들어주었다. 위 코드와 같이 서로 다른 두 수 num과 x - num에 대해 m[num]와 m[x - num]이 모두 true인 경우, 즉 쌍이 존재하는 경우 cnt의 값을 1 증가시켰다.

 위와 같이 코드를 작성하는 것이 조금 더 이해가 쉽고 직관적이라고 생각하지만, 아래와 같이 작성해도 같은 결과를 가져온다.

for (int i = 0; i < n; i++)
{
    if (m[x - v[i]] == true)
        cnt++;
    m[v[i]] = true;
}

  위 코드에서 cnt는 문제의 조건을 만족하는 쌍의 갯수를 표현한 변수이다.

 

두 가지 방식에서 모두 마지막에 cnt를 출력하면 문제가 해결된다.

cout << cnt << '\n';

전체 코드

1. 투 포인터

// https://www.acmicpc.net/problem/3273
// BOJ 3273번 - 두 수의 합

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int x;

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

    cin >> n;

    vector<int> v(n, 0);

    for (int i = 0; i < n; i++)
        cin >> v[i];

    cin >> x;

    sort(v.begin(), v.end());

    int start = 0;
    int end = n - 1;
    int cnt = 0;

    while (start < end)
    {
        if (v[start] + v[end] == x)
        {
            cnt++;
            end--;
        }
        else if (v[start] + v[end] > x)
            end--;
        else
            start++;
    }

    std::cout << cnt << '\n';

    return 0;
}

2. Hash Map

// https://www.acmicpc.net/problem/3273
// BOJ 3273번 - 두 수의 합

#include <iostream>
#include <vector>
#include <map>

using namespace std;

map<int, bool> m;

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

    int n;
    cin >> n;

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

    int cnt = 0;

    for (int i = 0; i < n; i++)
    {
        if (m[x - v[i]] == true)
            cnt++;
        m[v[i]] = true;
    }

    cout << cnt << '\n';

    return 0;
}