[파이썬] [이진탐색] 백준 1253 좋다

문제

https://www.acmicpc.net/problem/1253

1253번: 좋다

코드

n=int(input())
array=list(map(int, input().split()))
array.sort()

#결과값 저장 용도
count=0
for i in range(len(array)):
    #index i번째 제거하고
    temp=array[:i]+array[i+1:]
    left, right=0, len(temp)-1
    while left<right:
        if temp[left]+temp[right]==array[i]:
            count+=1
            break
        #값을 증가시켜야 하므로 left+1
        if temp[left]+temp[right]<array[i]:
            left+=1
        #값을 감소시켜야 하므로 right-=1
        else:
            right-=1
print(count)

시간 복잡도

입력 배열(N) * left~right(N) 이므로 O(N**2)

 

어려웠던 부분

계속 시간초과가 나왔고, 이진 탐색을 생각하는데 시간이 오래 걸렸다.