2407 두 용액

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

2470번: 두 용액

 

알고리즘 분류

1. 투포인터

 

아이디어

1. 2중 for문으로 구해 볼 수 있는 방법도 있을 것 같으나 시간초과가 날 것 같아 시도하지 않음

2. 투포인터 문제로 판단하고 용액의 수를 정렬 한 다음 왼쪽 끝과 오른쪽 끝을 투포인터로 두고 탐색을 시작

3. 포인터 상으로 용액 혼합 시 0에 가까우면 답 후보군 업데이트를 함

4. 현재 포인터 상으로 용액 혼합 시 음수이면 좀 더 양수에 가깝게 하기 위해 왼쪽 포인터를 오른쪽으로 옮기고 양수이면 좀 더 음수에 가깝게 하기 위해 오른쪽 포인터를 왼쪽으로 옮긴다.

 

코드

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

    solution.sort()

    left = 0
    right = len(solution) - 1

    ans_dist = 10000000000
    ans = []

    while True:
        if left >= right:
            break

        dist = solution[right] + solution[left]

        if ans_dist > abs(dist):
            ans = [str(solution[left]), str(solution[right])]
            ans_dist = abs(dist)

        if dist < 0:
            left += 1
        else:
            right -= 1

    print(" ".join(ans))