두 용액

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

2470번: 두 용액

문제요약:

숫자리스트 들이 주어질때 두 숫자를 합한값이 해서 0에 가장 가까운 두 숫자를 오름차순으로 출력하라

 

난이도:

골드5

 

소요시간:

30분

 

제출횟수:

매우많음

 

코딩:

import sys
from bisect import bisect_left
input  = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))

arr.sort()
piv = bisect_left(arr,0)
ans = []
if piv!= len(arr) and arr[piv] == 0:
    minus = arr[:piv]
    plus =  arr[piv+1:]
    if minus:
        ans.append([-minus[-1],minus[-1],0])
    if plus:
        ans.append([plus[0],0,plus[0]])
else:
    minus = arr[:piv]
    plus = arr[piv:]
    
if len(minus)>=2:
    ans.append([-minus[-1]-minus[-2],minus[-1],minus[-2]])
if len(plus)>=2:
    ans.append([plus[0]+plus[1],plus[0],plus[1]])
    
def cal():
    global ans
    A = minus
    B = plus
    for a in A:
        piv = bisect_left(B,-a)
        if piv!= len(B) and B[piv]==-a:
            return [0,a,B[piv]]
        else:
            if piv!=0:
                ans.append([abs(a+B[piv-1]),a,B[piv-1]])
            if piv!=len(B):
                ans.append([abs(a+B[piv]),a,B[piv]])
    return min(ans)

print(*sorted(cal()[1:]))

숫자들을 음수리스트와 양수 리스트로 나눈 후, 음수리스트를 하나씩 뽑아 양수리스트에 이진분류로 위치를 찾고 가장 가까운 갚들을 ans 에 넣어 ans에 최솟값이 나오면 두 수를 오름차순으로 출력하게 만들었습니다.

다만 이때 0이 리스트에 있었다면 0과 가장작은 양수, 0과 가장큰음수, 또한 가장작은 두 양수의 합, 가장큰 두 음수의 합을 추가적으로 넣어주었고, 이때 리스트에 접근할때 out of range오류가 많이떠서 제출을 많이 했습니다.

또한 중간에 혹시라도 절대값이 같다면 바로 출력하게 해주었습니다. 

 

다른사람 코드:

N = int(input())

solution=sorted(list(map(int, input().split())))

result = 9999999999999
start = 0
end = N-1
one = 0
two = 0

while start<end:
    temp = solution[start] + solution[end]
    zero = abs(temp)

    if result>zero:
        result=zero
        one = solution[start]
        two = solution[end]
    
    if temp>0:
        end-=1
    else:
        start+=1

print(one,two)

정렬 한뒤 맨왼쪽 과 맨오른쪽부터 투포인터로 답이 가까워 지는 방향으로 두 포인터들을 옮겼습니다.

그 둘을 더한값의 절대값이 현재 최저값보다 작다면 저장후, 모든 값들을 봅니다.