[ Python] BOJ 3273 : 두 수의 합

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

요구사항

1. 시간 제한 1초 지만 N<100,000 -> O(N**2) 는 힘들다. 
2. 메모리 제한 128M지만 100,000이라 리스트를 너무 남발하면 초과할 것. 

설계 1

1. combinations 모듈을 불러와서 2개의 조합을 구한다.
2. 자연수 x와 조합의 합이 같은 지 비교하여 count 한다.

구현 1

import sys
from itertools import combinations
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
n_list = tuple(map(int, input().split()))
compare_num = int(input())
count = 0

for combi in combinations(n_list, 2):
    if sum(combi) == compare_num:
        count += 1

print(count)

백준에서 실패 이유

• 다른 알고리즘 접근법이 생각이 안났다. (제한된 시간)
• 떠오른 건 2가지이다.
  • 빠르게 입력 받기
  • n_list을 초기화할 때 tuple 로 하기
• 그래도 안된다. 
• 그 이유는 combinations(n_list, 2)는 N개의 요소로부터 2개를 선택하는 모든 조합을 구하기 때문에 N(N-1)/2 즉, O(N**2)이 되는 것이다. 
• 따라서 다른 방법을 사용해야 한다.

설계 2

• 양 끝에서부터 비교해서 두수를 더하자 
• 근데 위 설계가 되려면 정렬 되어야 한다는 조건이 있다. 
  • 내가 알기로 파이썬의 정렬은 Timsort 알고리즘을 사용하는 데 시간복잡도가 낮았던 거 같다. 
• 만일 더한 두 수가 비교하려는 수보다 작으면 왼쪽 인덱스 + 1
• 크다면 오른쪽 인덱스 - 1 
• 만약 그래도 없다면?
  • 예외처리

구현 2

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
n_list = sorted(map(int, input().split()))
compare_num = int(input())
count = 0

left, right = 0, N-1

while left < right:
    combi_sum = n_list[left] + n_list[right]
    
    if combi_sum == compare_num:
        count += 1
        left += 1
        right -= 1
    elif combi_sum < compare_num:
        left += 1
    elif combi_sum > compare_num:
        right -= 1
    else:
        print("그런 조합 없다~")

print(count)