[백준] 2470 - 두 용액

1. 문제

2470번: 두 용액

2. 개요

주어진 용액들 중 두 개를 합성해 두 합성값을 최대한 0에 가깝게 하려고 한다.

이 때 두 용액의 특성값을 오름차순으로 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 용액들을 정렬하고 첫번째 용액부터 탐색을 시작한다.

선택된 용액의 다음 용액을 이분탐색의 포인터 1로 두고, 마지막 용액을 포인터 2로 두고 이분탐색을 실행하여 0에 가장 근접한 용액을 찾아나가는 것을 모든 용액에 대해 실행한다.

지금까지 가장 0에 근접한 조합을 찾았다면 용액1, 용액2를 현재 선택된 용액과, mid로 갱신한다.

모든 용액에 대한 탐색이 끝났다면 답을 출력한다.

3-2. PyPy

Python으로 제출 시 시간초과로 통과가 안된다.

import sys

N = int(sys.stdin.readline())

solutions = list(map(int, sys.stdin.readline().split()))

solutions.sort()

l = 0
mostclose = 2000000000
mostclose_l = -1
mostclose_r = -1

while l < len(solutions) -1:
    start, end = l + 1, len(solutions) - 1

    while start <= end:
        mid = (start + end) // 2

        if abs(solutions[l] + solutions[mid]) < mostclose:
            mostclose = abs(solutions[l] + solutions[mid])
            mostclose_l, mostclose_r = solutions[l], solutions[mid]

        if solutions[l] + solutions[mid] < 0:
            start = mid + 1

        elif solutions[l] + solutions[mid] > 0:
            end = mid - 1

        else:
            mostclose = 0
            mostclose_l, mostclose_r = solutions[l], solutions[mid]
            break

    l += 1

print(mostclose_l, mostclose_r)

3-3. C#

namespace boj_2470
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] solutions = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            Array.Sort(solutions);

            int l = 0;
            int mostclose_l = -1;
            int mostclose_r = -1;
            long mostclose = 2000000000;

            while (l < solutions.Length - 1)
            {
                int start = l + 1;
                int end = solutions.Length - 1;

                while (start <= end)
                {
                    int mid = (start + end) / 2;

                    if (Math.Abs(solutions[l] + solutions[mid]) < mostclose)
                    {
                        mostclose = Math.Abs(solutions[l] + solutions[mid]);
                        mostclose_l = solutions[l];
                        mostclose_r = solutions[mid];
                    }

                    if (solutions[l] + solutions[mid] < 0)
                        start = mid + 1;

                    else if (solutions[l] + solutions[mid] > 0)
                        end = mid - 1;

                    else
                    {
                        mostclose = 0;
                        mostclose_l = solutions[l];
                        mostclose_r = solutions[mid];
                        break;
                    }
                }

                l++;
            }

            Console.WriteLine($"{mostclose_l} {mostclose_r}");
        }
    }
}