백준 2470번 두 용액 파이썬 (투 포인터)

2023-02-20

백준 2470번 두 용액 파이썬

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

무엇?

산성 용액 특성값: 1부터 1,000,000,000까지의 양의 정수,
알칼리성 용액 특성값: -1부터 -1,000,000,000까지의 음의 정수
같은 양의 두 용액을 혼합한 용액의 특성값: 두 용액의 특성값 합

특성값이 0에 가장 가까운 용액을 만들어라

입력
첫째 줄 N (2 <= N <= 100,000)
둘째 줄부터 용액의 특성값을 나타내는 N개의 정수 (-1,000,000,000이상 1,000,000,000 이하)
(특성값은 모두 다름. 산성 용액만으로나 알칼리성 용액만 있는 경우도 있음)

출력
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값 오름차순 출력
0에 가깝게 만드는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력

왜?

정글 알고리즘 주차때 단번에 못 푼 것 재도전~!

어떻게?

내 코드

1. 용액의 특성값 오름차순 정렬
2. 투 포인터 검색
   1. start, end에서 검색 시작
   2. 0과 제일 가까운 수 찾기
      1. 0보다 작으면 start += 1 (둘 중 작은 값 업데이트)
      2. 0보다 크면 end -= 1 (둘 중 큰 값 업데이트)

import sys
min_comb = 1000000000*2
N = int(sys.stdin.readline())
values = list(map(int, sys.stdin.readline().split()))
values.sort()

def solution(values, min_comb):
    ans1 = 0
    ans2 = 0
    s = 0
    e = len(values) - 1

    if (values[0] > 0):
        ans1 = values[0]
        ans2 = values[1]
        print(ans1, ans2)
        return

    elif (values[-1] < 0):
        ans1 = values[-2]
        ans2 = values[-1]
        print(ans1, ans2)
        return

    while (s < e):
        sumvalue = abs(values[s] + values[e])
        if (sumvalue < min_comb):
            min_comb = sumvalue
            ans1 = values[s]
            ans2 = values[e]
        if min_comb == 0:
            break
        if values[s] + values[e] < 0:
            s += 1
        elif values[s] + values[e] > 0:
            e -= 1

    print(ans1, ans2)

solution(values, min_comb)

try-error

1. 절대값이 제일 작은 값을 찾는다? -> 0과 제일 가까운 수를 찾는다.
2. binary search로 구현하기
   쉬운 길을 어렵게 돌아가는 것이 아닌가하는 느낌을 받았음. 이분탐색 복습도 할 겸 다시 시도해보는 중!