(python) 백준 #2473 - [G3] 세 용액 : 이진탐색/투포인터

2473번: 세 용액

 

1. O(N*N*logN) : 2개 조합 완탐+바이너리서치

3개의 용액을 고르는 방법을 찾아야한다. 2개의 용액을 완전 탐색으로 고르고, 세 용액의 합이 0에 가장 가까워지도록 하는 마지막 용액을 찾는 방식을 채택했다.

2개의 용액을 완탐으로 찾는데 O(N*N), 마지막 용액을 binary search으로 찾는데 O(logN)이 걸린다.

(이진 탐색의 경우 재귀로 푼 경우 시간초과, 반복문으로 푼 경우 성공이었다. 반복문으로 쉽게 짤 수 있는 부분은 재귀를 사용하지 않는게 좋다.)

 

코드 1

import sys
def solution(input) :
    # 오름차순 정렬
    # 두개씩 선택
    # 뒤에꺼부터 맨 뒤까지 이진 탐색으로 0에 가까워지는걸 고르게
    # N 최악 5000
    # N*N*logN 

    def more_sim(a,b,target) :
            if abs(target-a) > abs(target-b) :
                return b
            else : return a

    def binary_find(s,target) :
        # li에서 target 값에 가까운 값 찾기
        e = len(L)-1

        
        # def recur(s,e, sim) : # 이진 탐색 재귀 -> 시간초과
        #     if s == e :
        #         if s >= len(li) :
        #             return li[-1]
        #         return more_sim(sim,li[s])
                
        #     mid = (e+s)//2
        #     if li[mid] == target :
        #         return target
        #     elif li[mid] < target :
        #         return recur(mid+1,e,more_sim(sim,li[mid]))
        #     else :
        #         return recur(s,mid,more_sim(sim,li[mid]))  
        # return recur(0,e,li[0])
        
        
        # 이진 탐색 반복문
        most_sim = L[s]

        while s <= e :
            mid = (s+e) // 2
            if L[mid] == target :
                return target
            
            most_sim = more_sim(most_sim, L[mid], target)
            if L[mid] < target :
                s = mid+1
            else :
                e = mid-1
        
        return most_sim


    N = int(input().rstrip())
    L = sorted(list(map(int, input().split())))
    most_sim = L[0]+L[1]+L[2]
    most_sim_items = L[:3]

    for i in range(N-2) :
        for j in range(i+1,N-1) :
            sim = binary_find(j+1,-(L[i]+L[j]))
            
            if abs(sim + L[i] + L[j]) < abs(most_sim) :
                most_sim = abs(sim + L[i] + L[j])
                most_sim_items = [L[i], L[j], sim]

    print(' '.join([str(i) for i in most_sim_items]))
input = sys.stdin.readline
solution(input)

 

2. O(N*N) : 1개 완탐+투포인터 (정석)

1을 완탐 하는데 O(N), 2,3을 찾는데 O(N)

 

코드 2.

import sys
def solution2(input) :
    N = int(input().rstrip())
    L = sorted(list(map(int, input().split())))
    most_0 = abs(L[0]+L[1]+L[2])
    most_0_items = L[:3]

    for p1 in range(N-2) :
        s = p1+1
        f = N-1
        while s < f :
            newsum = L[p1]+L[s]+L[f]
            if abs(newsum) < most_0 :
                most_0 = abs(newsum)
                most_0_items = [L[p1],L[s],L[f]]
            if newsum < 0 :
                s+=1
            elif newsum > 0 :
                f-=1
            else :
                break
        if most_0 == 0 :
            break
    print(*most_0_items)

input = sys.stdin.readline
solution2(input)

 

my solved.ac :

solved.ac