파이썬 알고리즘 150번 | [백준 3151번] 합이 0 - 투포인터 ;;

150. 합이 0

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

• 투 포인터로 접근해야 하는 문제

2) 코딩 설명

<내 풀이>

https://velog.io/@myway00/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-224%EB%B2%88-%EB%B0%B1%EC%A4%80-%EB%B2%88

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)

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

틀림 1

import sys

n=int(sys.stdin.readline())
lis=list(map(int,sys.stdin.readline().split()))
secondlis = lis.copy() #secondlis = lis 라고 쓰면 둘은 일심동체, 
#탐색 대상 리스트
tot = 0

for i in range(n) :
    pot1 = i
    for j in range(i+1,n) :
        pot2 = j
        if(-(lis[pot1] + lis[pot2])) in lis[pot2+1:] :
            tot+=lis[pot2+1:].count(-(lis[pot1] + lis[pot2]))
print(tot)

# for i in range(n) :
#     secondlis.remove(lis[i]) #lis[i] 는 중복 경우 위해 삭제(나 자신 빼고)
#     threelis = secondlis.copy()
#     for j in range(i+1, n) :
#         threelis.remove(lis[j])
#         tmp = lis[i] + lis[j]
#         if (-tmp) in threelis:
#             tot+=threelis.count(-tmp)
    
# print(tot)

• 시간초과가 걸린다.
• 이는 if x in list 구문때문일 것이라고 추측

틀림2 - 이분탐색으로 접근

import sys
n=int(sys.stdin.readline())
lis=list(map(int,sys.stdin.readline().split()))
lis.sort() #w작은 순으로 정렬
#탐색 대상 리스트
tot = 0
for i in range(n-2) :
    for j in range(n-1,i,-1) : #j는 맨 오른쪽부터 
        target =(-lis[i] + -lis[j])
        # print(target, i, j)
        lt = i
        rt = j
        while lt<=rt : 
            mid = (lt+rt)//2
            if lis[mid]==target:
                if mid==i:
                    break
                if mid ==j:
                    break
                tot+=1 
                # target을 찾으면? 바로 break 하면 안되지 
                #찾고 똑같은 애 있나 봐야지

                for k in range(mid+1,rt): #mid부터 rt 까지 검사 (rt 그 자체까지), 기존에 rt 였삼
                    if(lis[k]==target):
                        tot+=1
                for k in range(lt+1,mid): #range(lt+1,mid):
                    if(lis[k]==target):
                        tot+=1
                #print(tot)
                break
            elif lis[mid] < target:
                lt = mid +1
            elif lis[mid] > target :
                rt = mid - 1
print(tot)

                # print("find!")
                # print(lis)
                # print("value : ",lis[i], lis[j], lis[mid])
                # print("index : ",i, j, mid)
                # print("find!-----")

• 디버깅 중인데 어떤 테스트케이스가 틀린지 모르겠다..

<반성 점>

<배운 점>