[백준] 3151 : 합이 0

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

3151번: 합이 0

---

• 중복되지 않게 3명을 뽑아서 0 을 맞춰야 하는 문제이므로, 2명의 값이 정해지면 3번째 값은 자동으로 정해진다.
• 2명의 값을 정하기 위해 N * N 번 탐색을 하게 되면, 3번째 값을 찾기 위해선 이분탐색이더라도 logN 번이 필요하다.
• 그러나 투 포인터를 활용하면 N * N * logN 보다 더 빠른, N * N 으로 끝낼 수 있다.
• 첫번째 사람의 값을 고정해놓고(N), 나머지 두 학생의 값을 양쪽에 포인터를 두고 0 에 수렴하도록 옮겨주면 N 번이 걸린다.
• 이 때 값은 같더라도 다른 사람일 경우에 대해서는 세심한 예외처리가 필요하다.

---

N = int(input())
st = sorted(list(map(int, input().split())))
answer = 0

# 첫번째 수를 고정적으로 뽑아놓고 나머지 두 수 결정
for idx in range(N-2):
    # 두 수를 결정하기 위해 투 포인터를 써서 앞뒤로 범위를 줄여 O(N) 에 탐색
    target, l, r = -st[idx], idx + 1, N-1
    while l < r:
        cur = st[l] + st[r]
        # 만약 두 수가 우리가 원하던 값이라면
        if cur == target:
            curl, curr = st[l], st[r]
            # 그리고 두 수가 같은 수라면 그 수들로부터 2개를 뽑는 경우의 수만큼 팀 구성 가능(정렬되어있기 때문)
            if curl == curr:
                # 조합 계산식
                answer += (r-l+1)*(r-l)//2
                break
            # 두 수가 다른 수라면, 왼쪽포인터가 가리키는 수의 갯수 * 오른쪽포인터가 가리키는 수의 갯수
            else:
                dl, dr = 0, 0
                # 왼쪽 수의 개수를 구함
                while st[l] == curl:
                    dl += 1
                    l += 1
                # 오른쪽 수의 개수
                while st[r] == curr:
                    dr += 1
                    r -= 1
                answer += dl * dr
        elif cur < target:
            l += 1
        elif cur > target:
            r -= 1
print(answer)