📕문제

[Baekjoon] 1253.좋다

문제 설명

N개의 수 중 어떤 수가 다른 두 수의 합으로 나타낼 수 있을 때 그 수를 좋은 수라고 한다.
이 때 N개의 수 중에서 좋은 수가 몇개인지 구하는 문제다.
수가 같더라도 위치가 다르면 다른 수로 친다.
ex) ..., 0, 0, ... 에서 첫번째 0과 두번째 0은 다른 수로 취급한다.

---

📝풀이

import sys

read = sys.stdin.readline

N = int(read())
nums = sorted(list(map(int, read().split())))

count = 0
for i in range(N):
    target = nums[i]
    left, right = 0, N - 1

    while left < right:
        if left == i:
            left += 1
            continue
        if right == i:
            right -= 1
            continue

        total = nums[left] + nums[right]
        if total == target:
            count += 1
            break
        elif total < target:
            left += 1
        else:
            right -= 1
print(count)

• 투포인터를 사용하기 위해 숫자들을 정렬.
• nums의 각 숫자를 타겟으로 하여 투포인터를 진행한다.
  -left 또는 right가 타겟의 위치와 같다면 각 이동 방향으로 이동시킨다. (중복된 수 존재하기 때문)
• 두 수(left에 해당하는 수와 right에 해당하는 수)의 합이 타겟과 같다면 카운트 후 중단.
• 두 수의 합이 타겟보다 작으면 left이동, 크면 right이동.