[백준] 2467 - 용액

1. 문제

2467번: 용액

2. 개요

N개의 용액과 그 특성값들이 오름차순으로 주어진다.

두 용액을 합성해 가장 0에 가까운 특성값을 만들 때 사용한 두 용액의 특성값을 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

한 용액을 왼쪽부터 순서대로 탐색하고, 나머지 한 용액을 이분탐색을 이용해 찾는다.

이분탐색은 두 용액을 합친 특성값이 음수라면 오른쪽으로, 아니라면 왼쪽으로 이동하는데,

지금까지 구한 최적의 특성값보다 절대값이 작다면 답을 갱신해주면 된다.

3-2. Python

import sys

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

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

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#

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

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

        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}");
    }
}