[solved.ac 실버3] 3273_두 수의 합 (파이썬, 이분 탐색)

 

제한 사항

 

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제

 

---

나의 풀이

이 문제를 단순하게 더해서 나올 수 있는 모든 값을 리스트에 담아서 x(찾는 값)를 리스트의 모든 요소와 비교하며 찾는다면 최악의 경우 (수열의 크기 * 수열의 크기) * 2 = 20,000,000,000 만큼의 반복이 필요해서 시간 초과가 발생할 것이다.

이 문제는 이분 탐색으로 풀면 더 효율적으로 풀 수 있다.

1. 입력 받은 수열을 오름차순으로 정렬한다.
2. 수열을 순회한다.
   1. 현재 위치의 값이 a이고, 찾는 값이 x라고 할 때 이후의 위치에서 x-a가 존재하면 쌍을 만들 수 있는 것이다.
   2. 이때 이후의 위치에서 x-a를 찾는 과정을 이분 탐색으로 진행한다.

 

전체 코드

n = int(input())
arr = sorted(map(int, input().split()))
x = int(input())
answer = 0


def lower_bound(li, start, end, target):
    global answer

    while start <= end:
        mid = (start + end) // 2
        if li[mid] == target:
            answer += 1
            break
        elif li[mid] < target:
            start = mid + 1
        else:
            end = mid - 1


def solution():
    for i in range(n):
        if arr[i] > x: break
        t = x - arr[i]
        lower_bound(arr, i + 1, n - 1, t)


solution()
print(answer)

여기서 나는 한 단계를 추가했다.

현재 순차적으로 탐색하는 중 찾고자 하는 x보다 큰 값이라면 반복문을 종료한다. 이미 정렬되어 있기 때문에 x보다 큰 값을 다른 더 큰 양수와 더해서 x를 찾을 수 없기 때문이다.

 

채점 결과