[1253]'좋은 수' 구하기

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

투 포인터

• 수를 입력 받아 리스트에 저장한 후 정렬
• 투 포인터 i, j를 배열 A 양 끝에 위치시키고 이동 원칙을 활용해 탐색 수행

투 포인터 이동 원칙

• A[i] + A[j] > K: j--
• A[i] + A[j] < K: i++
• A[i] + A[j] == K: count++

탐색을 시작할 때, 제일 작은 수 A[i]와 제일 큰 수 Aj에서 시작하므로 판별 대상 수 K보다 클 확률이 높다. 이는 시작 포인터 i는 가만히 있고 종료 포인터 j가 점점 작아지는 방식으로 탐색한다는 것을 알 수 있다.

# N: 데이터 개수
# Result: 좋은 수 개수 저장 변수
# A: 수 데이터 저장 리스트
# A 리스트 정렬
N = int(input())
Result = 0
A = list(map(int, input().split()))
A.sort()

# find: 찾고자 하는 값
# 포인터 i, 포인터 j
for k in range(N):
    find = A[k]
    i = 0
    j = N - 1
    while i < j:  # 투 포인터 알고리즘
        if A[i] + A[j] == find: # find는 서로 다른 두 수의 합이어야 함을 체크
            if i != k and j != k:
                Result += 1
                break
            elif i == k:
                i += 1
            elif j == k:
                j -= 1
            elif A[i] + A[j] < find:  # 두 수의 합이 find 보다 작을 땐 시작 포인터를 크게
                i += 1
            else: # 두 수의 합이 find 보다 클 땐 종료 포인터를 작게
                j -= 1

print(Result)