두 수의 합 (이중 for문 / 투 포인터 / Hash)

제로베이스 백엔드 스쿨 김태원 님이 진행하신 알고리즘 특강 복습

 

자바로 진행했지만 코테는 파이썬으로 푸는 게 아직 익숙해서 파이썬으로 정리했다. 

 

문제: 길이가 n인 배열 중 다른 값 두 개를 더했을 때, 주어진 target 과 값이 같다면 두 값을 출력하고, 

없다면 [0, 0]을 출력. 단, 두 수를 합했을 때, target 이 되는 쌍은 하나만 존재.

 

1. 이중 for 문을 사용한 풀이 O(N^2) 

def solution (arr, target):
    for i in range(len(arr) -1):
        for j in range(i , len(arr)):
            if arr[i] + arr[j] == target:
                return [arr[i], arr[j]]
    
    return [0, 0]

 

2. 투포인터 O(nlogn)

def solution (arr, target):
    arr.sort()
    
    left  = 0
    right = len(arr) - 1;
    while left < right :
        if arr[left] + arr[right] == target:
            return [arr[left], arr[right]]
        elif arr[left] + arr[right] > target:
            right -= 1
        else:
            left += 1
    
    return [0, 0]

def solution (arr, target):
    candidate = set()
    
    for i in arr:
        if i in candidate:
            return([i, target - i])
        else:
            candidate.add(target - i)
    
    return [0, 0]

 

배열의 값을 한 번 돌면서  target 이 되려면 필요한 값 == target 에서 i 를 뺀 값 을 set 에 저장한다. 

 

만약에 배열에 i 가 있다면 앞에서 i와 더했을 때 target 이 되는 값이 있다는 의미이므로

i 와 target - i 를 return 하고 반복문을 종료한다. 

 

강의에서는 해시를 사용해서 푸는 방법이 있다고 하셨고, 구글링도 해시 테이블로 했지만 

어차피 target 에서 i 를 빼면 되니까 굳이 딕셔너리 사용해서 i 값을 저장할 필요가 없다고 생각했다.

 

set이나, 딕셔너리나 둘다 해시 테이블 쓰는 거니까 자기 하고 싶은 거로 하면 될 것 같다.