[백준] 3273번 두 수의 합 C언어

[실버 3]  3273  :  두 수의 합

[알고리즘 분류]

정렬, 투 포인터

 

 

1 초

128 MB

31308

11118

8429

35.184%

문제

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

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

 

[접근법]

처음에는 정렬을 쓰지 않고, 입력받은 숫자를 전부 배열에 들어온 순서대로 넣은 뒤에, 이중 반복문을 돌면서 두 원소의 합이 X와 일치하는지 체크했었다.

for (int i = 0; i < n - 1; i++)
{
    for (int j = i + 1; j < n; j++)
    {
    	if (arr[i] + arr[j] == x)
        {
        	count++;
        }
    }
}

이 방식은 굉장히 직관적이긴 하나, 시간 복잡도가 O(N^2)이기에 매우 느린 방식이다. 모든 원소를 탐색하며 두 원소의 합이 X인지 확인한다. 결국 시간초과가 떴다.

결국 시간을 줄이기 위해서는 위 방식대로 이중 반복문을 사용할 수 없었다. 다음으로 생각해낸 방법은, 배열을 정렬시킨 뒤, 반복문을 한 번만 돌리되, 인덱스를 i, j 두 개로 두는 방식이었다. 즉, 투 포인터 방식이다.

 

[풀이]

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

int compare(const void *a, const void *b)
{
    if (*(int *)a > *(int *)b)
        return 1;
    else if (*(int *)a < *(int *)b)
        return -1;
    else
        return 0;
}

int main()
{
    int n;
    int *arr;
    int x;
    int count;
    int i, j;

    scanf("%d", &n);
    arr = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &x);
    count = 0;
    qsort(arr, n, sizeof(int), compare);
    i = 0;
    j = n - 1;
    while (i < j)
    {
        if (arr[i] + arr[j] == x)
        {
            count++;
            if (arr[i + 1] - arr[i] < arr[j] - arr[j - 1])
            {
                i++;
            }
            else
            {
                j--;
            }
        }
        else if (arr[i] + arr[j] > x)
        {
            j--;
        }
        else if (arr[i] + arr[j] < x)
        {
            i++;
        }
    }
    free(arr);
    printf("%d\n", count);
}

i는 0부터, j는 제일 마지막 인덱스인 n-1부터 출발하면서 가운데로 향한다.

반복문은 i < j 일때까지만 돌리고, i가 j보다 크거나 같은 순간 탈출하게 한다.

조건문이 조금 복잡해 보일 수 있는데, arr [i] + arr [j] 값이 x와 일치한다면, count값을 1 올려주고, 다음에 이동시킬 포인터를 i로 할지, j로 할지 정해준다. 한 칸 이동했을 때 값의 차가 적은 쪽을 올려주었다.

arr [i] + arr [j] 값이 일치하지 않는다면, 그 값이 x보다 크거나 작은 여부를 파악해 포인터를 이동시켜 주었다.