[알고리즘] - 두 용액

문제

백준 - 두 용액 (골드 5)

풀이

1

  1. 값이 A라면, abs(리스트 값 + A) 인 리스트 L 생성
  2. 최솟값 구하기

2

  1. sort
  2. 값이 A라면 -A Search(이진 탐색)
  3. 있다면 정답 출력
  4. 없다면?
    • left나 right 중 더 가까운 값 찾기
  5. 반복
from bisect import bisect_left
sec = 2000000000

# 전체 용액의 수 N이 입력
N = int(input("용액의 수 : "))

# 용액의 특성값을 나타내는 N개의 정수
liquid = list(map(int, input().split()))

# sort
liquid.sort()

for i in liquid:
    # 1. 값이 A라면 -A Search(이진 탐색)
    left = bisect_left(liquid, -i)

    if left == 0:
        can = liquid[1]

    elif left == N:
        can = liquid[N-1]

    else:
        if liquid[left] == -i:
            fir = i
            sec = -i
            break
        else:
            if abs(i + liquid[left - 1]) > abs(i + liquid[left]):
                can = liquid[left]
            else:
                can = liquid[left - 1]

    if sec > can:
        fir = i
        sec = can

if fir > sec:
    fir, sec = sec, fir
print(fir, sec)

좋은 웹페이지 즐겨찾기