[백준 2470 파이썬] 두 용액 (골드 5, 투 포인터)

알고리즘 유형 : 투 포인터
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys, math
input = sys.stdin.readline

N = int(input())
arr = sorted(map(int, input().split()))

# 투 포인터
i = 0
j = N-1

# 갱신해나갈 혼합 용액 특성값 변수
spec_v = abs(arr[i] + arr[j])
# 갱신할 때마다 그 때의 두 용액 특성값 저장
result = [arr[i], arr[j]]

while i < j:
    x = arr[i]
    y = arr[j]
    x_abs = abs(arr[i])
    y_abs = abs(arr[j])
    tmp = abs(x + y)
    
    # 특성값 갱신
    if tmp < spec_v:
        spec_v = tmp
        result[0] = x
        result[1] = y
    
    # 합의 절댓값을 줄이기 위해서는,
    # 고른 두 수 중 절댓값이 큰 것을 줄이는
    # 방향으로 포인터를 옮겨주면 됨
    # 이는 두 수가 모두 양수이거나 음수일때도
    # 성립함
    if x_abs < y_abs:
        j -= 1
    elif x_abs > y_abs:
        i += 1
    else:
        break

print(*result)

풀이 요약

1. 포인터를 이동시키는 조건이 핵심인 문제이다.

2. 우선 포인터를 이동하면서, 매번 혼합 용액의 특성값을 절댓값이 더 작은 값으로 갱신해나갈 것이고, 동시에 그 때의 두 용액의 특성값을 저장해둘 것이다.

3. 혼합 용액의 특성값의 절댓값을 줄이기 위해서는, 포인터가 가리키는 두 용액의 특성값의 절댓값이 큰 것을 줄이는 방향으로 포인터를 옮겨주면 된다.

   이는 두 수가 모두 양수이거나 음수일때도 성립한다.

   만약 두 혼합 용액의 특성값이 같은 경우를 생각해보자.

   문제의 조건에서 모든 용액의 특성값은 서로 다르다고 했으므로, 만약 포인터가 가리키는 두 용액의 특성값이 모두 양수이거나 모두 음수라면, 이 둘의 특성값의 절댓값은 반드시 다르다.

   즉, 두 용액의 특성값이 같은 순간이 온다면 이 때는 반드시 음수와 양수라는 뜻이다.

   즉, 이 때의 혼합 용액의 특성값은 0이고, 바로 while문을 빠져나와 답을 출력해주면 된다.

배운 점, 어려웠던 점

• 투 포인터 활용력을 기를 수 있는 어렵지 않은 문제였다.