BOJ 3273 두 수의 합

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

3273번: 두 수의 합

문제를 마주쳤을 때 사고의 흐름. 
1. 수열을 정렬한다. sort() 써서. 
2. binary search를 써서 해볼까? n(수열의 크기)범위를 보니 이중for문 쓰면 시간초과 나오겠다..
3. sort 한 후, 수열의 각 요소(a_i)를 차례대로 훑으면서 수열에서 X-a_i (=target) 에 해당하는 값이 있는지 찾아야 한다. 
4. binary search를 돌리면서 mid가 x-a_i를 가리키는지 확인해보고, 없으면 -1, 있으면 result +=1. 

코드

N = int(input())
arr = list(map(int, input().split()))
X = int(input())
arr.sort()
 
def binary_search(target, start, end):
    if start>end:
        return -1
    mid = (start+end)//2
    if arr[mid]<target:
        return binary_search(target, mid+1, end)
    elif arr[mid]==target:
        return mid
    else :
        return binary_search(target, start, mid-1)
 
result = 0     
 
for i in arr:
    if binary_search(X-i, 0, len(arr)-1)>=0:
        result+=1 
print(result//2)

근데 이 문제는 이진탐색보다 훨씬 빠르게 풀 수 있다. for문 한번으로...^^; 
1. 수열을 입력받고, set으로 저장한다. (튜플 형태다. if x in arr 하려고..)
2. 수열 한 번 훑으면서 X-i가 수열에 있으면, result+=1 한다.

코드

N = int(input())
arr = set(map(int, input().split()))
X = int(input())
 
result = 0     
 
for i in arr:
    if X-i in arr:
        result+=1 
print(result//2)