[Python] 백준 3151 합이 0

1. 문제 링크

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

3151번: 합이 0

---

2. 문제 요약

세 팀원 코딩 실력이 0이 되는 경우의 수 구한다. 

 

---

3. 아이디어 정리

3명인데 투포인터를 진행해야 한다. -> 한 명씩 기준으로 잡고 그 안에서 투 포인터를 진행한다.

1. 합이 0이 되는 경우,

•  left값과 right 값이 같은 경우 해당 범위를 더한다. ⇒ 0이되는 right 학생수 얻어서 더하기
• left값과 right 값이 다른 경우 right에 해당되는 점수를 가진 학생 수 더하기

2. 합이 0보다 작은 경우 left + 1

3. 합이 0보다 큰 경우 right - 1

 

---

4. 문제 풀이

4-1. 내 풀이

"""
 세 팀원 코딩 실력 합 0
 팀을 얼마나 많이 만들 수 있는지 계산
 결과: 합이 0이 되는 3인조 만들
 주의: 같은 값이 연속적으로 나오는 경우 처리
"""
import sys
from collections import Counter

n = int(sys.stdin.readline())  # 학생 수
arr = list(map(int, sys.stdin.readline().split()))  # 학생 코딩 실력
arr.sort()
cnt_ = Counter(arr)  # 해당 점수에 해당하는 학생 수 얻기 
result = 0
# 학생을 한명 씩 돌린다.
for i, a in enumerate(arr):
    left, right = i + 1, n - 1
    while left < right:
        sum_ = arr[left] + arr[right] + arr[i]
        # 1. 점수 총합이 0인 경우, 같은 값이 있는 것에 대한 처리 필요
        if sum_ == 0:
            #  left값과 right 갑이 같은 경우 해당 범위 저장. -4 -4 2 2 2 
            if arr[left] == arr[right]:
                result += right - left
                        # 다른 경우 right 값에 대한 개수 합
            else: 
                result += cnt_[arr[right]]
            left += 1
                # 2. 점수 총합이 0 보다 큰 경우 
        elif sum_ > 0:
            right -= 1
                # 3. 점수 총합이 0 보다 작은 경우
        elif sum_ < 0:
            left += 1

print(result)

 

---

5. 결론

• 3포인터는 없다. 그래서 한 학생을 기준으로 투 포인터를 진행해야 한다.
• 생각보다 오래 걸린 문제...😫