[백준 3273] 두 수의 합

[BanApp]

pypy3

import sys
n = int(sys.stdin.readline())
arr = []

arr = list(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline())

arr.sort()

cnt = 0
s = 0
e = n-1
while s < e:

    if arr[s] + arr[e] >= m:
        if arr[s] + arr[e] == m:
            cnt = cnt + 1
        e = e-1

    elif arr[s] + arr[e] < m:
        s = s + 1

print(cnt)

가장 단순한 방법은 이중 반복문을 사용해서 전체 탐색을 하는것인데 그럴경우 배열의 크기가 매우 커질경우 시간초과가 나오게 된다.
따라서 배열에서 양쪽 끝지점에서 시작하는 두개의 포인터 s,e를 만든다.
또한 이는 오름차순 정렬일때 사용가능하므로 입력받은 배열을 오름차순으로 정렬해준다.
만약 arr[s] + arr[e]가 목표값(m)보다 작을 경우 s의 인덱스를 하나 증가 시켜 합의 값을 증가 시킨다.
목표값보다 크거나 같을경우는 다음과 같다.
같을 경우는 원하는 값을 찾은것이기 때문에 cnt 변수에 추가해주고 e의 인덱스를 하나 감소시킨다.
클 경우 e의 인덱스 값을 하나 감소시켜 전체 합의 값을 감소시켜서 다시 탐색한다.