백준 3151 : 합이 0 (Python)

본문 링크

🔑『처음 시도했지만 틀렸던 코드』

import sys
input=sys.stdin.readline

N=int(input())
L=sorted(list(map(int,input().split())))

count=0
for i in range(N-2):
    total=L[i]
    start=i+1 ; end=N-1

    while start<end:

        if L[start]+L[end]+total==0:
            count+=1
            start+=1

        elif L[start]+L[end]+total<0:
            start+=1

        elif L[start]+L[end]+total>0:
            end-=1


print(count)

🔑『수정한 코드』

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

N=int(input())
L=sorted(list(map(int,input().split())))
count=0
for i in range(N-2):
    start=i+1 ; end=N-1
    while start<end:
        if L[start]+L[end]+L[i]>0:
            end-=1
        else:
            if L[start]+L[end]+L[i]==0:
                if L[start]==L[end]:
                    count+=end-start
                else:
                    K=bisect_left(L,L[end])
                    count+=end-K+1
            start+=1

print(count)

📌 어떻게 3명의 합이 0인 지접을 찾을 것인가?

삼분탐색도 가능할꺼같으나 N의 범위가 1 ≤ N ≤ 10000 이기 때문에
반복문으로 1부터 N까지 돌린다음에 매개변수를 2개를 사용하여 투 포인터를 사용했다.

처음에는 문제가 아주 평범하게 느껴져서 일반적인 투 포인터 알고리즘을 작성하였으나 4%에서 틀렸다고 떴다.

틀린 코드의 반례는 아래와 같다.

• 입력
  8
  -10 5 5 5 5 5 5 5
• 출력
  6

중복되는 경우의 수 를 고려하지않았다.
틀린코드에서 입력을 저렇게 해버리면 total 이 -10일때

인덱스 1부터 N-1까지만 고려하기 때문에 총 6이 나온다.

이때 라이브버리 from bisect import bisect_left 을 사용하면
bisect_left(L,L[end]) 를 사용했을때 리스트 L에서 L[end]값의 개수를 찾는다

세 수의 합이 0 일때
L[start]==L[end]일때는 그냥 end-start를 해주고
그렇지 않을때는 end 인덱스에 리스트의 L[end]개수를 빼주고 1을 더한값을 count에 더해준다.

이후 start를 증가시킨다.