[백준] 용액

출처:: www.acmicpc.net/problem/2467

분류:: 투포인터, 이진탐색

 

1. 문제 이해 및 해결과정

- 투포인터 => O(n) - 범위조심  -1,000,000,000 이상 1,000,000,000 이하의 수가 입력되는데, 산성이나, 알칼리성만으로 이루어진 입력이 들어올 수가 있으므로 최대가 2,000,000,000 이 될 수 있다.

 

2. 풀이방법

  1. 투포인터 [python]

#용액
#https://www.acmicpc.net/problem/2467
import sys
sys.stdin = open("input.txt","r")
n=int(input())
arr=list(map(int,input().split()))
minv=2e10
l=0
r=n-1
while l < r:
    sum=arr[l]+arr[r]
    if abs(sum)<abs(minv):
        minv=sum
        a=arr[l]
        b=arr[r]
    if sum<0:
        l+=1
    else:
        r-=1
print(a,b)

  2. 이진탐색 [python] O(nlogn)

#용액
#https://www.acmicpc.net/problem/2467
import sys
sys.stdin = open("input.txt","r")
n=int(input())
arr=list(map(int,input().split()))
minv=2e10

for i in range(n): #현재를 기준으로 오른쪽 용액중에 이진탐색
    l=i+1
    r=n-1
    while l<=r:
        mid=(l+r)//2
        #현재용액과 찾은용액(mid)의 절댓값의 합이 최소
        if abs(arr[i]+arr[mid])<abs(minv):
            minv=abs(arr[i]+arr[mid])
            a=arr[i]
            b=arr[mid]
        #-arr[i]에 가장 근접하거나 같은 원소 찾기
        if arr[mid]==-arr[i]: #같으면 0
            break
        elif arr[mid]<-arr[i]: #왼쪽값
            l=mid+1
        else:
            r=mid-1
print(a,b)

 

3. 오답원인

  1. 범위

 

4. 알게된 점