백준 세 수의 합과 이분탐색 활용하기

백준 이분탐색 풀이의 가장 빠른 풀이방법은 이분탐색을 활용하는 것이다.

기존 풀이

정수 배열 arr이 주어지고 a,b,c,d가 배열 arr의 원소일 때 a+b+c=d를 만족하는 d의 최댓값을 구하면 된다.

a,b,c,d 모두 4중 for문으로 구하면 된다. 즉 시간복잡도는 O(n^4)이다.

이분탐색을 이용한 풀이

아래의 코드는 정답이 아니다 ㅠ

백준문제의 입출력을 처리해주지 않고 오프라인 환경에서 테스트케이스만 해결해보았다.

정확히는 a+b를 저장한 배열을 소팅해주어야 가능하다.

import bisect
def solution(n,array):
    sum=set();
    max=0;
    for i in range(0,n):
        for j in range(0,n):
            sum.add(array[i]+array[j]);
    for i in range(0,n):
        for j in range(i+1,n):
            if(bisect.bisect(list(sum),(array[j]-array[i]))):
                if(max<j):
                    max=j;
    return array[max];

식을 a+b+c=d에서 a+b=d-c로 바꾸었다.

이후 a+b를 set에 담은 후 d-c를 이분탐색하여 최대값을 구하였다.

시간복잡도를 크게 줄일 수 있다..!