[BOJ] 2470. 두 용액 (🥇 , 이분탐색/투 포인터)

문제

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

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

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

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

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

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

풀이

두 포인터 문제라고하는데 처음 봤을 때 투 포인터가 뭔지 몰라서 유튜브의 도움을 좀 받았다. https://www.youtube.com/watch?v=ttLRltNDiCo

대충 두 개의 인덱스를 가지고 정답에 접근해가는 방식으로 푸는 거 같았다. 이분탐색으로도 풀 수 있다고 해서 두 가지 방식으로 다 풀어보는 풀이

조건

1. 서로 다른 두 용액을 혼합하는거지 두 용액이 반드시 알칼리성 / 산성이여야 할 필요 없다. 산성 두 용액을 합쳐도 0에 가깝기만 하면 된다
2. 0이 될 수 있는 값을 찾는 게 아니라 0에 가장 가까우면 된다
3. 용액이 가질 수 있는 최대 값이 1,000,000,000이므로 최대값 설정을 1e9로 하게 되면 에러난다

투 포인터

• 정렬하기
  - 막연하게 두 용액이라길래 산성/알칼리로 나누어서 힙 정렬쓰고 난리를 칠 뻔했는데 그런 거 상관없고 0에 가깝기만 하면 되는 거였음. 일단 정렬하지 않으면 값을 브루트포스로 list 두 번 돌아야 하기 때문에 무조건 정렬을 해준다 파이썬의 sort() 메서드는 최선의 경우 O(n)의 시간복잡도를 가짐
• 가장 왼쪽을 left, 가장 오른쪽을 right로 놓고 두 개의 인덱스 값을 조정해가며 최선의 값을 찾는다. 여기서 최선의 값은 두 용액 차이의 절대값이 0과 가장 근접한 값
• [-99, -4, -2, 1, 98] 로 정렬하게 되었을 때 가장 왼쪽의 -99와 오른쪽 98을 더하면 -1이 나오게 된다. 0에 근접한 값을 구하기 위해서는 어떻게 해야 될까? 생각해보면 음수 값의 절대값이 너무 크기 때문에 최종적으로 음수 값이 나오게 된 것이라는 걸 알 수 있다. 현재 정렬된 순서를 봤을 때 left 값을 +1하면 음수의 절대값이 줄어들게 된다. 이런 방식으로 접근하는 것이다.
• 반대로 -4 + 98 = 95로 이번엔 양수의 절대값이 너무 크다 즉 right -= 1을 해주면 되는 것
• 두 용액 차이의 절대값은 왔다갔다 하게 된다. 어쨌든 이런식으로 구해나가면 적어도 양수로만 커지거나 음수로만 커지지는 않고 0으로 수렴하는? 식으로 진행된다. 실제로 도중에 구해지는 차이값은 [-1, 96, 2,-3] 였다
• 리스트가 아무리 길어도 O(N)에서 값을 찾을 수 있음

    solution.sort()
    l, r = 0, N-1
    min_diff, min_sols = 1e13, []
    while l < r:
        tmp = solution[l] + solution[r]
        if abs(tmp) < min_diff:
            min_diff = abs(tmp)
            min_sols = [l, r]
        
        if tmp >= 0:
            r -= 1
        else:
            l += 1

이분탐색

풀이 참고

• 나무 자르기나 랜선 자르기 같은 이분탐색일 줄 알았는데 전혀 아니었고... 리스트 전체를 돌면서 그 값의 왼쪽에 있는 값들 중에서 이분 탐색해서 0에 가장 가까워지는 값을 찾는 방식
• 전체 리스트를 탐색하고(N), 동시에 그 리스트를 이분탐색도 하기 때문에(logN) 전체 시간복잡도는 O(NlogN)
• mid 값을 찾아나가면서도 중간에 계속 min_diff값을 갱신해줘야 한다 여기서는 이분탐색이 끝나도 최종적으로 차이가 0이 되는 값을 찾을 수 없을 수도 있기 때문이다

def sol(N, solution):
    solution.sort()
    
    min_sols, min_diff = [solution[0], solution[N-1]], 1e13
    for i in range(N-1):
        sol1 = solution[i]
        l, r, m = i+1, N-1, 0
        while l <= r:
            m = (l+r)//2
            tmp_sum = sol1+solution[m]

            if abs(tmp_sum) < min_diff:
                min_diff, min_sols = abs(tmp_sum), [sol1, solution[m]]
            if tmp_sum < 0:
                l = m+1
            else:
                r = m-1
    
    print(*min_sols)

N = int(input())
solution = list(map(int, input().split()))
sol(N, solution)

전체 코드

투 포인터

# 92ms

def sol(N, solution):

    solution.sort()
    l, r = 0, N-1
    min_diff, min_sols = 1e13, []
    while l < r:
        tmp = solution[l] + solution[r]
        print(tmp)
        if abs(tmp) < min_diff:
            min_diff = abs(tmp)
            min_sols = [l, r]
        
        if tmp >= 0:
            r -= 1
        else:
            l += 1

    print(solution[min_sols[0]], solution[min_sols[1]])

N = int(input())
solution = list(map(int, input().split()))
sol(N, solution)

이분탐색

def sol(N, solution):
    solution.sort()
    
    min_sols, min_diff = [solution[0], solution[N-1]], 1e13
    for i in range(N-1):
        sol1 = solution[i]
        l, r, m = i+1, N-1, 0
        while l <= r:
            m = (l+r)//2
            tmp_sum = sol1+solution[m]

            if abs(tmp_sum) < min_diff:
                min_diff, min_sols = abs(tmp_sum), [sol1, solution[m]]
            if tmp_sum < 0:
                l = m+1
            else:
                r = m-1
    
    print(*min_sols)

N = int(input())
solution = list(map(int, input().split()))
sol(N, solution)

반례

3
-1 0 1

-1 1


4
-3 -1 1 10

-1 1


5
-100 -50 20 40 80

-50 40


4
-3 1 2 10

-3 2