[3273] 두수의 합

3273번: 두 수의 합

N개의 원소 중 2개를 더했을 때 X 값이 되는 조합의 수를 구하는 문제이다.

일일히 2개를 픽해서 더하는 방식도 가능하겠지만, N이 크기 때문에 좀 더 효율적인 방식이 좋을 것이다.

그래서 사용하는 것이 투 포인터이다.

투 포인터 포인터를 2개 둬서 조건에 따라 해당 포인터를 이동시키면서 조건에 맞는 지 체크하는 형식이다.

우선, 투 포인터에서 중요한 점은 2개의 포인터 중 어떤 걸 옮길지 조건을 제시해주는 것이다. 원소들을 정렬하고, 포인터를 양쪽 끝에 둔다면…

첫번째 포인터는 가장 작은 값, 두번째 포인터는 가장 큰값을 가지게 된다.

포인터에 해당하는 두 수의 합이 X보다 작다면, 앞의 포인터를 이동 시키고 큰 경우는 뒤의 포인터를 이동시키는 방식으로 진행한다.

같은 경우는 어떻게 할까…?

같은 경우는 두 포인터를 모두 이동시킨다.

물론 모든 경우의 수를 보지는 않기에 시간 복잡도가 낮고, X에 가까워지도록 코드를 작성했기 때문에 X에 해당하는 경우의 수를 모두 찾을 수 있다.

풀이

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline())
    nums = list(map(int, sys.stdin.readline().split()))
    X = int(sys.stdin.readline())
    start = 0
    end = N-1
    count = 0
    nums = sorted(nums)
    while start < end:
        sums = nums[start] + nums[end]
        if sums == X:
            count += 1
            start += 1
            end -= 1
        else:
            if sums < X:
                start += 1
            else:
                end -= 1

    print(count)