백준 3273번 두 수의 합: C언어 풀이

백준 3273번 두 수의 합 문제의 C 언어 풀이 해설입니다.
배열을 이용해 숫자의 등장 여부를 체크하는 방식으로, 시간복잡도 O(n)으로 두 수의 합이 특정 값이 되는 쌍의 개수를 구하는 방법을 설명합니다.

전략

원소의 등장 여부를 기록하는 Lookup 배열

주어진 합이 10, 수열이 2, 6, 4 순서라고 해보자.

첫번째 원소는 2다. Lookup 배열에서 10 - 2, 8을 찾아본다. 없다.
2를 Lookup 배열에 등록한다.

두번째 원소는 6이다. Lookup 배열에서 10 - 6, 4를 찾아본다. 있다.
6을 Lookup 배열에 등록한다.

세번째 원소는 4다. Lookup 배열에서 10 - 4, 6을 찾아본다. 있다.
조건을 만족하는 쌍을 발견했으므로 카운트를 더해준다.
찾은 경우 굳이 Lookup 배열에 등록할 필요가 없다. 어짜피 모든 수는 한번씩만 등장한다.

코드

#include <stdio.h>
#include <stdlib.h>

#define MAX_ARR_SIZE 100000
#define MAX_ELEMENT_VALUE 1000000

// Status of an element in the lookup table
enum element_status
{
    NOT_FOUND,
    FOUND
};

int main(void)
{
    int num_elements;
    scanf("%d", &num_elements);

    int arr[MAX_ARR_SIZE];
    for(int i = 0; i < num_elements; i++)
    {
        scanf("%d", &arr[i]);
    }

    int target_sum;
    scanf("%d", &target_sum);

    // Element larger or equal to target_sum cannot make a pair, thus ignored.
    int lookup_size = (target_sum < MAX_ELEMENT_VALUE) ? target_sum + 1 : MAX_ELEMENT_VALUE + 1;
    // Initiate lookup table to NOT_FOUND
    int *lookup = (int *)calloc(lookup_size, sizeof(int));

    // # of (ai + aj = target_sum) for (i < j < MAX_ARR_SIZE)
    int pairs_count = 0;

    for(int i = 0; i < num_elements; i++)
    {
        // Ignore elements with out of range correspondents
        if(arr[i] < target_sum && target_sum - arr[i] < lookup_size)
        {
            // Check for corresponding element
            if(lookup[target_sum - arr[i]] == FOUND)
            {
                pairs_count++;
            }
            else
            {
                lookup[arr[i]] = FOUND;
            }
        }
    }

    printf("%d\n", pairs_count);
    free(lookup);
}