3273: 두 수의 합

1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000

n은 입력받은 수열, x는 두 수열의 합

메모리 128MB 

데이터의 개수가 1,000만 단위가 넘어가지 않도록...

 

1. itertools 라이브러리 사용해서 combination을 만들어서 x를 만드는 조합 개수를 찾자

-> 메모리 초과 (최대 10만 수열에서 2개 원소로 조합을 만들어서 리스트에 저장하면 대략 50억 가량의 데이터가 나옴....

from itertools import combinations
import sys
n = int(sys.stdin.readline().rstrip())
data = list(map(int, sys.stdin.readline().rstrip().split()))

x = int(sys.stdin.readline().rstrip())
data = list(combinations(data, 2))
cnt = 0
for i in data:
  if sum(i) == x:
    cnt += 1
print(cnt)

 

2. 메모리 초과나오니까 data의 개수를 최대한 줄여보자. 두 수를 더해도 x가 안되거나 x를 넘어가면 data에서 해당 원소를 빼자

-> 메모리 초과

from itertools import combinations
import sys
n = int(sys.stdin.readline().rstrip())
data = list(map(int, sys.stdin.readline().rstrip().split()))#최대 100만
data.sort()

x = int(sys.stdin.readline().rstrip())

#나름 data 개수 줄이기 위함.... 
if min(data) + max(data) < x:
  data.remove(min(data))
elif max(data) > x:
  data.remove(max(data))
data = list(combinations(data, 2)) #위에서 data가 제거되지 않으면 어차피 메모리 초과
cnt = 0
for i in data:
  if sum(i) == x:
    cnt += 1
print(cnt)

 

3. 조합을 없애고 이중 반복문으로 수열을 하나씩 더해보자

-> 시간 초과 (예상했음. O(N^2)이 될텐데 최대 N = 10만 ^ 2)

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
data = list(map(int, sys.stdin.readline().rstrip().split()))
x = int(sys.stdin.readline().rstrip())
data.sort()
data = deque(data)

if min(data) + max(data) < x:
  data.popleft()
elif max(data) > x:
  data.pop()

cnt = 0
for i in range(len(data)):
  for k in range(i+1, len(data)-1):
    if data[i] + data[k+1] == x:
      cnt += 1

print(cnt)

 

4. for문을 어떻게든 줄이려고 bisect 라이브러리 사용해서 x에 data에서 가장 작은 원소를 뺀 수가 data의 어느 자리에 들어갈 지 index 저장후 그 index를 마지막으로 두고 for문 돌림

-> 시간초과 (x= 2000000이고 data[0] = 1이면 소용없음)

import sys
from collections import deque
from bisect import bisect_right

n = int(sys.stdin.readline().rstrip())
data = list(map(int, sys.stdin.readline().rstrip().split()))
x = int(sys.stdin.readline().rstrip())
data.sort()
sub = x - data[0]
idx = bisect_right(data, sub)
#x와 data[0]이 같은 경우 idx=1, x가 data[0]보다 작을 경우 idx =0


cnt = 0
for i in range(idx+1):
  if idx == 0 or idx == 1:
    break
  for k in range(i+1, len(data)-1):
    if data[i] + data[k+1] == x:
      cnt += 1

print(cnt)

 

5. 검색 후 투 포인터로 해결하는 거라고 알아냄. data를 정렬한 후 right와 left를 초기화. x보다 크면 right -= 1, 작으면 left += 1, x와 같으면 right -=1 또는 left +=1 하기

-> 많아야 O(n) + O(nlogn)복잡도가 나옴. ( O(nlogn) : sort())

import sys

n = int(sys.stdin.readline().rstrip())
data = list(map(int, sys.stdin.readline().rstrip().split()))
x = int(sys.stdin.readline().rstrip())
data.sort()

left = 0
right = len(data)-1
cnt = 0

while left < right:
  if data[left] + data[right] < x:
    left += 1
  elif data[left] + data[right] > x:
    right -= 1
  elif data[left] + data[right] == x:
    cnt += 1
    right -= 1

print(cnt)