배열을 이용하면 O(n) 으로 쉽게 풀 수 있는 문제이다.
mem 배열을 이용해서 순차적으로 등장하는 요소 x 들을 배열의 x번째에 기록해두었다가 mem[x] = 1 그 이후에 등장하는 요소와 더해서 k (두 수의 합) 가 되는지를 확인하는 것이다. mem[k-i] == 1 만약 k=8로 주어졌는데 앞에서 3이란 값이 저장되었고 이번에 나오는 요소가 5라면 mem[8-5] 값은 1(혹은 True) 이기 때문에 빠르게 정답을 확인할 수 있다.
가장 처음 풀었을 때는 if 문의 순서를 잘 못 짜서 시간이 더 많이 걸렸다. 그러니깐 처음부터 mem 리스트에 기록을 하고 난 뒤에, 판별을 해버리게 되면 k/2 == i 인 경우에는 두 수의 합으로 기록되지 말아야 하는데도 cnt가 되어버리는 문제가 있었다.
if int(x)-int(i)==int(i):
continue와 같은 불 필요한 연산이 한 번 더 이루어지는 셈이었다. 그래서 아래와 같이 if 문에 먼저 검사 한 이후에 mem에 기록함으로써 하나의 단계를 없애 주었다.
그 다음으로 흔하게 발생하는 것은 IndexError인데, k가 1000001 이상의 값이 나오고 i 가 작은 값이 나올 때에는 mem 의 길이가 1000001 밖에 되지 않기 때문에 이를 초과하는 경우가 발생한다. (예:k=2000000, i=1 인 경우) 물론 mem 사이즈를 최대 2000001로 두면 간단히 풀리는 문제이지만 이 경우에는 불필요한 연산을 하는 것 뿐만 아니라 (판별 , mem에 저장) 메모리도 두 배나 더 쓰는 것이다. 효율적이지 않으므로 아래와 같이 if k-i >= 1000001: 단계만 사용하는 것으로 효율성을 높일 수 있다.
마지막으로 else를 사용한 부분은 그냥 if 문 밖으로 꺼내도 상관은 없는데 만약 해당 숫자를 가지고 합 여부를 판별했다면 그 숫자는 앞에 등장한 숫자와 함께 합을 구성하는 것이고 두 번 다시 그 숫자를 필요로 하지 않기 때문에 mem 에 저장할 필요도 없어서 else 처리를 했고 결론적으로 if 문 밖에서 mem을 저장하는 것보다 5ms 빠르다. (trivial)
n = int(input())
arr = list(map(int, input().split()))
k = int(input())
mem = [0] * 1000001 # 1백만 1 이하로만 기록해도 된다. 그 이상은 기록 할 필요가 없음.
cnt = 0
for i in arr:
if k-i >= 1000001:
continue
elif mem[k-i]:
cnt += 1
else:
mem[i] = 1
print(cnt)