[백준] 1253 - 좋다 Python

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

1253번: 좋다

N 개의 수 중 자기 자신이 아닌 다른 두 수의 합으로 나타낼 수 있는 수를 구하는 문제다.

- 입력을 받은 N 개의 수를 정렬한다. (nlogn)

- 투 포인터 알고리즘을 이용해 0 번째 인덱스부터 N-1 번째 인덱스까지 두 수를 조합해 현재 수를 만들 수 있는 경우를 완전탐색한다.

- 한번 탐색한 숫자에 대해 다시 불필요한 탐색을 하지 않도록 각 숫자별로 해시테이블에 다른 두 수의 합으로 만들 수 있는지 1, -1 로 저장한다.

 

자기 자신이 아닌 두 수의 합으로 나타낼 수 있어야 하기 때문에 start 또는 end 가 자기 자신일 경우 continue 로 넘어갈 수 있도록 한다.

from sys import stdin
from collections import defaultdict

def find(x):
    global i
    start = 0
    end = N-1
    while start < end:
        if start == i:
            start = i+1
            continue
        if end == i:
            end = i -1
            continue
        s = arr[start] + arr[end] 
        if s == x:
            return True
        elif s > x:
            end -= 1
        else:
            start += 1
    return False

hash_table = defaultdict(int)

N = int(stdin.readline())
arr = list(map(int,stdin.readline().split()))
arr.sort()

cnt = 0
for i in range(N):
    is_exist = hash_table[arr[i]]
    if is_exist == 1:
        cnt += 1
    elif is_exist == -1:
        continue
    else:
        if find(arr[i]):
            hash_table[arr[i]] = 1
            cnt += 1
        else:
            hash_table[arr[i]] = -1

print(cnt)