[백준] 3151번 합이 0

💡문제접근

• 이분 탐색 + 투 포인터를 이용한 문제였다. 일단 이분 탐색을 수행하려면 정렬이 수행된 상태여야 한다는 뜻이므로 오름차순 정렬을 수행한 다음 bisect 라이브러리의 bisect_left, bisect_right를 사용해서 문제를 해결할 수 있다. 접근을 설명하면 아래와 같다.
• 보충 문제로 [[백준] 7453번 합이 0인 네 정수]가 있다. 이것도 풀어봐야겠다.

💡테스트케이스

입력
10
2 -5 2 3 -4 7 -4 0 1 -6

• 1) 오름차순 정렬을 수행하면 -6 -5 -4 -4 0 1 2 2 3 7으로 정렬이 수행된다.
• 2) 이중 for문을 이용해서 투 포인터를 만들고 나머지 하나의 값을 bisect 라이브러리를 이용해서 찾는다.
  ex. 예를 들어 [-4, 2]가 뽑힌 상황에서 나머지 한 명을 더 뽑아야 하는데 이 떄 뽑히는 경우의 수는 1이 된다.

💡코드(메모리 : 118620KB, 시간 : 12516ms, PyPy3로 제출)

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

N = int(input())
coding = list(map(int, input().strip().split()))
coding.sort()
cnt = 0

for a in range(N-1):
    for b in range(a+1, N):
        temp = (coding[a] + coding[b]) * -1
        # a와 b사이에 존재하는 값 중에서 temp와 연산하여 값이 0이 나오는 최초의 temp값의 인덱스를 구함
        Left = bisect_left(coding, temp, a+1, b)
        # a와 b사이에 존재하는 값 중에서 temp와 연산하여 값이 0이 나오는 마지막의 temp값의 인덱스를 구함
        Right = bisect_right(coding, temp, a+1, b)
        cnt += Right - Left
print(cnt)

💡소요시간 : 24m

📌이진 탐색 라이브러리 bisect란 무엇일까?

• Python에서 이진 탐색을 수행할 때 직접 이진 탐색을 수행하는 코드를 작성해서 탐색을 하는 방법도 존재하지만 bisect 라이브러리가 존재한다.
• bisect 라이브러리에는 bisect_left, bisect_right가 존재하는데 기능에 대해서 설명하면 다음과 같다.

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.

The returned insertion point i partitions the array a into two halves so that all(val < x for val in a[lo : i]) for the left side and all(val >= x for val in a[i : hi]) for the right side.

key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value.

If key is None, the elements are compared directly with no intervening function call.

Changed in version 3.10: Added the key parameter.