python 알고리즘 - 조건을 충족하는 두 개의 숫자를 빠르게 찾습니다.

질문의 전제는 이런 숫자가 2개가 있어야 한다는 것입니다

답은 하나도 적지 않겠습니다... 생각나지 않으실 겁니다.

첫 번째 제가 생각한 건 2번 솔루션 끝에 있는 해시 테이블이었는데요

(실제로는 타겟만큼 큰 배열을 만들어볼까 생각도 했습니다. 존재한다면 인덱스를 쓰되 찾고 싶으면 찾으면 됩니다. 다 2차원 배열이 필요한데 나중에 타겟이 너무 크면 공간낭비가 되지 않을까요... 그래서 Dict로 바꿨습니다)

나중에 보니 질문은 두 개의 숫자만 필요합니다. - -

확장 질문이 더 재미있습니다.

3개 찾기 어렵지는 않겠지만 다른 건 잘 모르겠어서 추가하고 싶습니다. ...

1. 2차원 배열

def find_pair(A, target):
    B = [[] for i in range(target + 1)]
    for i in range(0, len(A)):
        if A[i] <= target:
            B[A[i]].append(i)
    for i in range(0, target / 2 + 1):
        if len(B[i]) != 0 and len(B[target - i]) != 0:
            print(i, B[i], target-i, B[target-i])
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

2. 사전

def find_pair(A, target):
    B = {}
    for i in range(0, len(A)):
        if A[i] <= target:
            if not B.has_key(A[i]):
                B[A[i]] = [i]
            else:
                B[A[i]].append(i)
    for i in range(0, target / 2 + 1):
        if B.has_key(i) and B.has_key(target-i):
            print(i, B[i], target-i, B[target-i])
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)

3. 책에 나온 인덱스를 돌려준다는 뜻이 뭔지 아세요... 게을러서 내장된 것만 사용하는데...

def find_pair(A, target):
    A.sort()
    i, j = 0, len(A) - 1
    while i < j:
        s = A[i] + A[j]
        if s == target:
            print(i, A[i], j, A[j])
            i += 1
            j -= 1
        elif s < target:
            i += 1
        else:
            j -= 1
  
if __name__ == "__main__":
    A = [0, 1, 1, 2, 11, 8, 3, 4, 5, 6, 7, 8, 9, 10]
    find_pair(A, 9)