[BOJ] Q2467 용액

[BOJ] Q2467 용액

Question

Language: Python

Difficulty: Gold 5

알칼리성 용액과 산성 용액을 섞어서 최대한 중성에 가까운 용액에 만드는 실험과 관련된 문제이다.

알카리성은 -를 산성은 +를 나타내며, 각각 크기는 성질의 세기를 의미한다. 이때, 두개를 더하여 0이 되면 이는 중성임을 뜻한다.

주어진 용액에 대해서, 2개를 선택해서 가장 가까운 용액을 찾는 과정은 two_pointer 형태로 풀이가 가능하다.

start,end=0,n-1부터 시작해서 용액[start]+용액[end]을 더하면서 합의 크기를 비교하면서 start,end 범위를 좁혀나간다. 만약 용액의 합이 양수이면 이는 산성임을 의미하기 때문에 산성의 세기를 낮추기 위해 end-1을 하고, 음수이면 이와는 반대로 start+1을 하면서 비교를 진행한다.

while start<end:
    #용액을 섞는다. 
    temp=numbers[start]+numbers[end]
    
    #기존에 찾은 용액보다 더 중성에 가까운 경우
    if abs(temp) < min_sum:
        min_sum=abs(temp)
        answer=[numbers[start],numbers[end]]
        #중성이 되면, 더 이상 탐색을 진행하지 않아도 된다.
        if min_sum==0:
            break
    #산성인 경우 --> 산성의 세기를 낮춘다.    
    if temp >0:
        end-=1
    #알카리성인 경우 --> 알칼리성의 세기를 낮춘다.
    else:
        start+=1

Solution 1

from math import inf

def solution():
    start,end=0,n-1
    answer=[]
    min_sum=inf

    while start<end:
        temp=numbers[start]+numbers[end]

        if abs(temp) < min_sum:
            min_sum=abs(temp)
            answer=[numbers[start],numbers[end]]
            if min_sum==0:
                break
        
        if temp >0:
            end-=1
        else:
            start+=1
        
    print(*answer)

if __name__ =="__main__":
    n=int(input())
    numbers=list(map(int,input().split()))
    solution()

Solution 2

해당 문제는 이분탐색을 응용해서 풀이하는 것도 가능하다.

from math import inf

def binary_search(l,r,value):
    min_sum=inf
    min_index=0
    while l <= r:
        mid=(l+r)//2
        temp=value + numbers[mid]

        if abs(temp) < min_sum:
            min_sum=abs(temp)
            min_index=mid
            if min_sum==0:
                break
                
        if temp <0:
            l=mid+1
        else:
            r=mid-1

    return min_sum,numbers[min_index]


def solution():
    min_sum=inf
    answer=[]
    for i in range(n-1):
        number=numbers[i]
        temp,value=binary_search(i+1,n-1,number)

        if temp < min_sum:
            min_sum=temp
            answer=[number,value]
    
    print(*answer)
            


if __name__ =="__main__":
    n=int(input())
    numbers=list(map(int,input().split()))
    solution()