[백준/Python] 2467번: 용액

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

 

 

풀이

1. 만약 모든 수가 양수라면 첫 번째와 두 번째의 합이 가장 0에 가깝다.
2. 만약 모든 수가 음수라면 마지막에서 첫 번째와 마지막에서 두 번째의 합이 가장 0에 가깝다.
3. 음수와 양수가 섞여 있다면 다음 과정을 진행한다.

가장 큰 음수와 가장 작은 양수를 left, right로 설정한 뒤 two pointer를 사용한다.

만약 left와 rigth를 더한 값이 음수라면 더욱 큰 값을 구해야 하므로 right를 증가시킨다.

만약 left와 rigth를 더한 값이 양수라면 더욱 작은 값을 구해야 하므로 left를 감소시킨다.

이 과정을 범위가 벗어날 때까지 반복한다.

반복을 마친 뒤 두 가지 반례를 고려해야 한다.

음수와 양수가 섞여있지만 양수 중 가장 작은 두 값과 음수 중 가장 큰 두 값을 고려해야 한다.

def get_closest_zero_number(a, b):
    a = abs(a)
    b = abs(b)
    return min(a, b)
# 모두 양수인지
def is_all_plus(arr):
    return arr[0] >= 0

# 모두 음수인지
def is_all_minus(arr):
    return arr[-1] <= 0

# 처음으로 양수가 되는 인덱스 구하기 
def get_first_plus_index(arr):
    n = len(arr)
    for i in range(n):
        if arr[i] >= 0:
            return i

def solution(arr):
    n = len(arr)
    if is_all_plus(arr):
        return 0, 1
    if is_all_minus(arr):
        return -2, -1
    
    # 처음으로 양수가 되는 인덱스를 구한다.
    first_plus_idx = get_first_plus_index(arr)
    left, right = first_plus_idx-1, first_plus_idx
    res = abs(arr[left]+arr[right])

    res_left, res_right = left, right
    # 범위에서 벗어나지 않을 때까지 반복한다.
    while left >= 0 and right < n:
        sum_value = arr[left]+arr[right]
        new_number = abs(sum_value)
        
        # 0에 더 가깝다면 갱신
        if new_number < res:
            res = new_number
            res_left, res_right = left, right
            
        # 만약 양수라면 더욱 작은 값을 넣어서 0에 가까운지 확인한다.
        if sum_value > 0:
            left -= 1
            continue
        # 만약 음수라면 더욱 큰 값을 넣어서 0에 가까운지 확인한다.
        if sum_value < 0:
            right += 1
            continue
        
        # 0이라면 종료
        return (res_left, res_right)
    if first_plus_idx < n-1:
        new_number = abs(arr[first_plus_idx]+arr[first_plus_idx+1])
        if new_number < res:
            res = new_number
            res_left, res_right = first_plus_idx, first_plus_idx+1
    elif first_plus_idx > 1:
        new_number = abs(arr[first_plus_idx-1]+arr[first_plus_idx-2])
        if new_number < res:
            res = new_number
            res_left, res_right = first_plus_idx-2, first_plus_idx-1
    return (res_left, res_right)

n = int(input())
arr = list(map(int, input().split())) 
left, right = solution(arr)
print(arr[left], arr[right])