[백준 2470] 두 용액 (Python)

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

2470번: 두 용액

나의 풀이(실패)

 

n = int(input())
INF = int(1e9)
li = list(map(int,input().split()))
li = sorted(li)
min_sum = INF
for i in li:
  temp = li.copy()
  temp.remove(i)
  start = 0
  end = len(temp)
  while start < end:
    mid = (start + end)//2
    if i < 0 and abs(i + temp[mid]) < min_sum:
      min_sum = abs(i + temp[mid])
      end = mid - 1
      answer = [i, temp[mid]]
    elif i < 0 and abs(i + temp[mid]) > min_sum:
      start = mid + 1
    elif i > 0 and abs(i + temp[mid] < min_sum):
      min_sum = abs(i + temp[mid])
      start = mid + 1
      answer = [i, temp[mid]]
    elif i > 0 and abs(i + temp[mid] > min_sum):
      end = mid - 1
print(sorted(answer))

 

시간 초과가 나게 되었다.

 

투포인터 활용 문제 풀이

n = int(input())
INF = int(2e9) + 1
li = list(map(int,input().split()))
li = sorted(li)
min_sum = INF
start = 0
end = n -1
answer = []
while start < end:
  if abs(li[start] + li[end]) < min_sum:
    answer = [li[start], li[end]]
    min_sum = abs(li[start] + li[end])
  if li[start] + li[end] < 0:
    start += 1
  else:
    end -= 1
print(' '.join(list(map(str,answer))))

 

INF 를 int(2e9) +1로 사용한 이유는 문제의 조건에서 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하라고 하였고  산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다고 하였기 때문에 최소 -2,000,000,000 최대 2,000,000,000이기 때문이다. 

 

참고 블로그 : https://bladejun.tistory.com/97

백준 2470번 두 용액 (python, 파이썬)