[알고리즘] 두 용액 백준 2470 python

문제 바로가기

풀이

투포인터 문제입니다.
보통 절대값이 비슷한 음수와 양수를 합쳐야 0과 가까운 수가 나오므로 배열을 정렬한 후 양쪽 끝에서부터 비교해나가면 되는 문제입니다.

1. 포인터 두 개를 왼쪽 끝과 오른쪽 끝으로 설정합니다.
2. 첫 값으로 answer에 맨 왼쪽과 오른쪽을 더한 값의 절대값을 넣어줍니다.
3. final에는 2번의 각각의 값들을 배열에 넣어둡니다.
4. 이제 두 포인터가 만나기 전까지 반복문을 돌립니다.
5. 왼쪽 포인터와 오른쪽 포인터를 인덱스로 가지는 배열의 값을 더한 후 절대값 처리를 합니다.
6. 그 값이 현재 저장되어있는 answer보다 작다면 업데이트해줍니다.
7. sum이 음수라면 left를 한칸 오른쪽으로 당겨주고, 양수라면 right를 한칸 왼쪽으로 당겨줍니다.(0과 가깝게 만들기 위해서)

n = int(input())
arr = list(map(int, input().split(' ')))
arr.sort()

left = 0
right = n-1

answer = abs(arr[left] + arr[right])
final = [arr[left], arr[right]]


while left < right:
    left_val = arr[left]
    right_val = arr[right]

    sum = left_val + right_val
  
    if abs(sum) < answer:
        answer = abs(sum)
        final = [left_val, right_val]
        if answer == 0:
          break
    if sum < 0:
        left += 1
    else:
        right -= 1

print(final[0], final[1])