2467 용액

https://www.acmicpc.net/problem/2467

2467번: 용액

 

알고리즘 분류

1. 투포인터

2. 이분탐색

 

아이디어

1. N이 1,000,000이므로 두 용액을 고르는 가장 쉬운 방법인 O(n^2)시간 복잡도로는 시간 초과 위험이 있음

2. 용액을 상수대로 정렬하고 가장 작은 수와 가장 큰 수에 포인터를 둔 다음 두 용액을 혼합했을 때의 결과를 보고 0에 가까운 수면 정답셋에 저장

3. 혼합 용액의 수가 음수이면 0에 가깝게 만들어주기 위해서 low 포인터를 오른쪽으로 옮기고 양수이면 high 포인터를 왼쪽으로 옮김

 

if __name__ == "__main__":
    N = int(input())
    solutions = list(map(int, input().split(" ")))

    solutions.sort()

    low = 0
    high = len(solutions) - 1

    res = []
    res_num = 0

    while True:
        if low >= high:
            break

        mix = solutions[high] + solutions[low]
        temp = abs(mix)

        if len(res) == 0:
            res = [str(solutions[low]), str(solutions[high])]
            res_num = temp
        else:
            if temp <= res_num:
                res = [str(solutions[low]), str(solutions[high])]
                res_num = temp

        if mix <= 0:
            low += 1
        else:
            high -= 1

    print(" ".join(res))