[백준/Python] 3273. 두 수의 합

 

• 리스트에서 자신을 제외한 두 수의 합이 x가 되는 경우의 수를 출력하는 문제이다.
• 2중 for문(O(n^2))으로 풀면 시간초과가 나오기에 투 포인터 알고리즘(O(n))을 통해 풀었다. 

import sys
input = sys.stdin.readline      # 입력 시간을 줄이기 위한 코드

N = int(input())
arr = list(sorted(map(int,input().split()))) # 왼쪽과 오른쪽에서 가운데로 오는 투포인터 알고리즘을 쓸 것이기에 정렬을 하고 시작하였다.
target = int(input())
cnt = 0
start, end = 0, N-1

while end > start:              # start와 end가 같아진다면 끝나도록 제한
    tmp = arr[start] + arr[end] # tmp에 두 수의 합을 저장

    if tmp > target:            # tmp가 target보다 크다면 end의 인덱스를 -1
        end -= 1
    else:
        start += 1              # tmp가 target보다 작다면 start의 인덱스를 -1
        
    if tmp == target:           # tmp가 target과 같다면 cnt를 올림
        cnt += 1

print(cnt)