배열: 두 수의 합

두 수의 합

문제 설명

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

def solution(nums, target):
	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]

문제 풀이

• 이 문제를 처음 보게 되면 가장 먼저 생각나는 방식은 brute force 방식이다. 하지만 brute force로 계산하게 될 경우 O(n^2)의 시간 복잡도이기 때문에 배열이 길어질 경우 시간이 초과될 가능성이 있다. 그래서 이 문제를 접근할 때는 최대한 시간복잡도를 줄이는 방향으로 진행하는 것이 좋다.
• in 방식으로 접근하는 것도 좋긴 하지만, in으로 하게 되면 모든 배열을 확인하는 과정이 거쳐지기 때문에 완벽하게 최적화 된 것은 아니다.
• 그래서 dictionary를 기반으로 진행하게 될 경우, 탐색을 하게 되면 O(1)로 탐색이 되기 때문에 이 방식을 사용하는 것이 좋다.