[백준][C++] 1253: 좋다

문제

풀이

모든 합을 저장하여 이분 탐색으로 진행할 경우, 자기 자신이 합에서 사용되었는지 알 수 없기에 사용할 수 없다.

 

unordered_map 사용

• 모든 합을 피연산자와 함께 unordered_map에 저장한다. 
• input이 unordered_map에 있는지 확인하고, 피연산자로 자기 자신이 사용되었는지 확인한다.

두 포인터 사용

• 입력된 수열을 정렬하고 양 옆에서 두 포인터 알고리즘을 시작한다. 
• 같은 수가 합에 사용되면 안 되므로 start < end일 때까지만 반복한다. 
• 자기 자신은 합에 포함되면 안 되므로 start와 end를 조정

코드

unordered_map 사용

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

using namespace std;

vector<int> inputs;
unordered_map<int, vector<pair<int, int>>> sums;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;
        inputs.push_back(temp);
    }

    // 가능한 모든 경우를 unordered_map에 저장
    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
            // 합과 함께 피연산자들을 저장한다.
            sums[inputs[i] + inputs[j]].push_back(make_pair(i, j));
        }
    }

    int answer = 0;
    for (int i = 0; i < N; ++i)
    {
        // inputs[i]가 unordered_map에 있는지 확인
        int find_num = inputs[i];
        if (sums.find(find_num) != sums.end())
        {
            bool flag = false;
            for (auto operand : sums[find_num])
            {
                // 피연산자로 자기 자신이 들어있는지 확인
                if (operand.first != i && operand.second != i)
                {
                    flag = true;
                    break;
                }
            }

            if (flag)
            {
                answer++;
            }
        }
    }

    cout << answer;

    return 0;
}

 

두 포인터 사용

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

using namespace std;

vector<int> inputs;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int temp;
        cin >> temp;
        inputs.push_back(temp);
    }

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

    int answer = 0;
    for (int i = 0; i < N; ++i)
    {
        int find_num = inputs[i];

        int start = 0;
        int end = inputs.size() - 1;
        // 두 수가 같으면 안 되므로 start < end일 때 까지만 반복
        while (start < end)
        {
            // 자기 자신은 합에 포함되면 안된다.
            if (start == i)
            {
                start++;
                continue;
            }
            if (end == i)
            {
                end--;
                continue;
            }

            // 합이 find_num과 같을 경우 answer 증가
            int sum = inputs[start] + inputs[end];
            if (sum == find_num)
            {
                answer++;
                break;
            }
            
            // 합이 더 작을 경우 start 증가
            // 합이 더 클 경우 end 감소
            if (sum < find_num)
            {
                start++;
            }
            else
            {
                end--;
            }
        }
    }

    cout << answer;

    return 0;
}