파이썬 알고리즘 224번 | [백준 3151번] 합이 0 - 투포인터 ** 꼭 다시 풀어보자

224. 합이 0

1) 어떤 전략(알고리즘)으로 해결?

• 이분탐색

2) 코딩 설명

<내 풀이>

from collections import Counter
import sys

n = int(sys.stdin.readline().strip())
students = list(map(int,sys.stdin.readline().strip().split()))
students.sort()
std_counter = Counter(students) 
# 리스트나 셋을 인자로 넘기면 각 항목을 키로 해서 개수
res = 0
for i in range(n) : 
    s,e=i+1,n-1 # 나이 후 ~ 끝 전 
    target = -students[i]
    # print(i,target)
    while s<e : 
        cmp = students[s] + students[e]
        if cmp < target : 
            s+=1 # 증가하여야 하므로 시작점 오른쪽으로 

        elif cmp == target : # 중복 수 걸러줘야 하지 
            if students[s]==students[e] : # 만약 양쪽 같으면 
                res+= e-s # -4 0 (2) 2 2 (2) 3 => 인덱스 2와 5, 5-2 = 3
            else : 
                res+= std_counter[students[e]] #students[s] 
            s+=1 # e-=1

        else : 
            e-=1 # 감소하여야 하므로 끝점 왼쪽으로 

print(res)

<내 틀렸던 풀이, 문제점>

• 너무도 당연하게 시간 초과과

from itertools import combinations
import sys

n = int(sys.stdin.readline().strip())
students = list(map(int,sys.stdin.readline().strip().split()))
cnt = 0
comb = combinations(students, 3)
for co in comb : 
    if sum(co)==0 : 
        cnt+=1
print(cnt)

• 46%에서 틀림

from collections import Counter
import sys

n = int(sys.stdin.readline().strip())
students = list(map(int,sys.stdin.readline().strip().split()))
students.sort()
std_counter = Counter(students) 
# 리스트나 셋을 인자로 넘기면 각 항목을 키로 해서 개수
res = 0
for i in range(n) : 
    s,e=i+1,n-1# 나이후 ~ 끝 전 
    target = -students[i]
    while s<e : 
        cmp = students[s] + students[e]
        if cmp < target : 
            s+=1 # 증가하여야 하므로 시작점 오른쪽으로 

        elif cmp == target : # 중복 수 걸러줘야 하지 
            
            if students[s]==students[e] : # 만약 양쪽 같으면 
                res+= e-s # -4 0 2 2 2 3 => 인덱스 2와 4, 4-2 = 2
            else : 
                res+= std_counter[students[s]]
            e-=1

        else : 
            e-=1 # 감소하여야 하므로 끝점 왼쪽으로 

print(res)

<반성 점>

<배운 점>

(+) https://ryu-e.tistory.com/29