[ 3151 ] [ 이진 탐색 ] 합이 0

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

3151번: 합이 0

---

풀이 과정

---

1. 임의의 수를 두개 고른 다음, 두 수의 합의 부호를 반전시켜 준다.
2. 반전시켜 준 값이 고른 두개의 수 위치 뒤에 있는지 확인한다.
   1. 있다면, 값이 여러개일 수 있으므로 이분 탐색을 두번 진행한다.
   2. bisect_left로 왼쪽 위치를 구해주고, bisect_right로 오른쪽 위치를 구해준 다음 두 값의 차이만큼 정답에 더해준다.
   3. bisect_left의 경우 값이 존재하는 맨 왼쪽 위치가 리턴되고, bisect_right의 경우 값이 존재하는 맨 오른쪽 위치 + 1이 존재하므로 bisect_right의 결과에서 bisect_left의 결과를 빼주면 동일한 값의 개수가 나온다.

 

---

소스 코드

---

import sys
from bisect import bisect_left, bisect_right

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
cache = set(numbers)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        target = -(numbers[i] + numbers[j])
        if target in cache:
            answer += bisect_right(numbers, target, j+1, N) - bisect_left(numbers, target, j+1, N)

print(answer)