[Python] 백준 3273번 두 수의 합

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

문제 

 

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

 

나의 해결법

 

처음에는 단순히 이중 for문을 통해서 해결했다. 하지만 역시나 시간초과가 발생하였다.

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
x = int(sys.stdin.readline()) # 목표값

for i in range(n):
    for j in range(i+1, n):
        if a[i] + a[j] == x:
            cnt += 1

print(cnt)

 

그래서 두번째 방법 !

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
x = int(sys.stdin.readline()) # 목표값

cnt = 0
left, right = 0, n-1

a.sort() # 먼저 정렬을 해줌

while left != right: # 왼쪽과 오른쪽이 만나지 않는 동안
    if a[left] + a[right] == x: # 합이 목표값과 같으면 cnt 증가
        cnt += 1
        left += 1

    elif a[left] + a[right] > x: # 합이 목표값보다 크면 오른쪽 인덱스를 -1
        right -= 1
        
    else: # 합이 목표값보다 작으면 왼쪽 인덱스를 + 1
        left += 1
        
print(cnt)