두 수의 합

문제

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

 

· 입출력 예 

nums	target	return
[2, 7, 11, 15]	9	[0, 1]

---

풀이

1. 브루트 포스로 계산

def twoSum(nums: list[int], target: int) -> list[int]: 
    for i in range(len(nums)): 
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

브루트 포스란 배열을 2번 반복하며 모든 조합을 더해 일일이 확인해보는 무차별 대입 방식으로, 비효율적인 풀이법에 해당한다. nums 배열을 이중 탐색하며 nums[i], nums[j] 두 값을 더했을 때 target이 되는 경우의 i, j를 반환한다.

 

2. in을 이용한 탐색

def twoSum(nums: list[int], target: int) -> list[int]:
    for i, n in enumerate(nums):
        complement = target - n 
        
        if complement in nums[i+1:]:
            return [nums.index(n), nums[i+1:].index(complement) + (i+1)]

모든 조합을 비교하지 않고 정답 (타겟)에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색하는 문제로 변경하여 풀 수 있다. nums[i+1: ]부터 검색을 하기 때문에, 반환 시에 i + 1을 더하여 반환해준다.

 

3. 첫 번째 수를 뺀 결과 키 조회

def twoSum(nums: list[int], target: int) -> list[int]:
    nums_map = {}
    for i, num in enumerate(nums):
        nums_map[num] = i
        
    for i, num in enumerate(nums):
        if target - num in nums_map and i != nums_map[target - num]:
            return [i, nums_map[target - num]]

nums_map 딕셔너리의 키에 값을, 값에 인덱스를 저장하였다. 이후, target - num 값이 딕셔너리에 존재하는지 여부와 target - num의 index가 자기 자신이 아닌 경우 (두번째 수)에 i와 두 번째 수의 인덱스를 반환한다.

 

4. 조회 구조 개선

def twoSum(nums: list[int], target: int) -> list[int]:  
    nums_map = {} 
    for i, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target - num], i]
        nums_map[num] = i

딕셔너리 저장과 조회를 하나의 for문으로 합쳐서 처리하였다. 이 경우 전체를 모두 저장할 필요 없이 정답을 칮게 되면 함수를 바로 빠져나올 수 있지만, 두 번째 값을 찾기 위해 매번 비교해야 하기 때문에 앞선 풀이에 비해 성능상의 큰 이점은 존재하지 x

---

Info

1. 파이썬 내부 함수로 구현된 in은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 빨리 실행된다.

2. 입력받은 배열의 두 수의 합이 n인지 여부를 판단할 때는 n - array[i] 값이 배열에 들어있는지 여부를 파악하는 것이 두 값을 찾기 위해 노력하는 것 (브루트 포스)보다 훨씬 수월하다.