백준 #2467 - [G5] 용액 : binary search (이진탐색)

(python3)

2467번: 용액

 

투포인터, 이진 탐색

완전 탐색을 진행하면 $O(N^2)$ 으로 시간초과가 발생합니다. 정렬된 상태로 입력이 주어지므로 이진 탐색을 활용하면 O(N*logN) 으로 줄일 수 있습니다.

 

추가로 섞을 용액 두개 다 양수인 경우 가장 작은 합 조합은 가장 작은 양수 두개가 됩니다. 음수의 경우도 마찬가지 입니다.

가장 큰 음수 두개, 가장 작은 양수 두개 조합을 확인하고 음수+양수 조합을 확인하면 시간을 더 단축시킬 수 있을 것 같습니다.

음수 + 양수 조합은 모든 음수에 대해서 양수 부분만 이진탐색을 진행하면 될 것 같습니다.

 

코드

import sys
def solution(input) :
    N = int(input().strip())
    L = list(map(int, input().split()))
    mix = (0,0) # 섞었을때 0에 가장 가까운 조합의 인덱스 저장 
    mix_min = 3000000000 # 섞었을 때 값
        
    for i in range(N) :
        if L[i] >= 0 : # 양수가 되는 순간, 양수+양수 조합의 최소는 가장 작은 양수 둘
            if i+1<N and abs(L[i] + L[i+1]) < mix_min :
                mix = (i,i+1)
            break
            
        # 이진탐색으로 i 의 최적 짝 찾기
        s = i+1
        e = N-1
        while s<=e :
            mid = (s+e) // 2

            if L[i]+L[mid] == 0 : # 0이면 바로 출력
                print(L[i],L[mid])
                return
            
            if abs(L[i]+L[mid]) < mix_min : # 최소 갱신
                    mix_min = abs(L[i]+L[mid])
                    mix = (i,mid)
				
            # 이진탐색
            if L[i]+L[mid] < 0 :
                s = mid+1
            else :
                e = mid-1
    
    print(L[mix[0]],L[mix[1]])

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac