백준(C) 2470번 [두 용액]

두 용액 2470번

 

접근방법

두 용액 문제는 서로 다른 n개의 정수가 주어졌을때, 두 수의 합이 0에 가까운 수를 찾는 문제이다.

보통 이럴때 가장 쉽게 푸는 방법은 전체의 경우의 수를 비교하는 것이지만(브루트포스), 안타깝게도 대부분의 문제는 그러면 시간초과가 나오게 설정이 되어있다. 그러므로 시간을 최대한 효율적이게 쓰는 알고리즘을 사용해야한다. 

방법은 두개 생각했다. 한개는 이진탐색이고 한개는 투포인터이다. 이진 탐색을 사용했을때 따로 조건문을 많이 사용해야할것 같아서 투포인터로 풀었다.

 

투 포인터는 간단하게 설명하면 움직이는 포인터를 두 개로 만들것이다.

만약 이 문제처럼 1차원 배열로 예를 들면

 

 

이렇게 생각할수있다. 조건에 따라 포인터 1을 움직일지 포인터 2을 움직일지 고르면된다.(이 방법은 배열을 한번 순회해서 배열을 n만큼 순회하는 것보다 효율적이다)

이 문제에서 가장 중요한것은 투포인터를 사용하기전에 정렬이 필요하다는 것이다. 그렇지 않으면 시간을 효율적이게 사용할수 없다.(정렬을 하지않으면 애초에 조건문 설정할때 많은 힘이 든다.) 

정렬에는 c언어에서 사용하는 qsort를 사용했다. c++ 문법을 사용하면 sort를 쓰면되지만 c에서는 sort가 없다.

그래서 cmp 정렬 함수도 선언해서 사용했다

qsort는 다양한 데이터 타입을 정렬 할수있게 설계가 되었기에 void를 사용한다. 그후 return 에는 자신이 원하는 데이터 타입의 정렬을 적어야 하므로 int*를 사용했다.  그렇게 되면 오름차순 정렬을 할수있다.(return 에 적힌 연산은

두 값이 같음 = 0 , a가 b보다 작음 = -1, a가 b보다 큼 = 1 라고 생각할수있다.) 

투포인트 연산은 매우 간단하다.

0과 매우 가까워야 하니깐 일단 0이면 바로 while문에 탈출한다. 두 포인터가 가르키는 배열의 수의 합이 양수면 더 작은 값으로 이동하니 오른쪽 포인터를 줄이고 음수면 왼쪽 포인터를 증가 시켜 더 큰값으로 이동시킨다.

그리고 만약 왼쪽 포인터가 오른쪽 포인터를 넘어서게 되면 종료하면된다. 그 후 출력하면 끝이다. 

 

이 문제도 구상이 구현보다 어려운 문제이다.(구상도 알고있으면 어렵지 않다)

 

코드는 다음과 같다.

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

int cmp(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

int main(void)
{
    int n, num[100001];
    scanf("%d", &n);
    for (int a = 0; a < n; a++)
    {
        scanf("%d", &num[a]);
    }

    qsort(num, n, sizeof(int), cmp);
    int l = 0, r = n - 1, min = INT_MAX, l_num, r_num;

    while (l < r)
    {
        int sum = num[l] + num[r];
        if (abs(sum) < abs(min))
        {
            min = sum;
            l_num = num[l];
            r_num = num[r];
        }

        if (sum > 0)
        {
            r--;
        }
        else if (sum < 0)
        {
            l++;
        }
        else
            break;
    }

    printf("%d %d", l_num, r_num);

    return 0;
}