두 수의 합 리트코드

리트 코드 두수의 합

두 수의 합

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

• 입력

nums = [2, 7. 11, 15], target = 9

• 출력

[0, 1]

여기서 문제를 풀때 브루트 포스나 in을 이용한 탐색, 첫 번째 수를 뺀 결과 키 조회 하는 방법으로 풀 수 있다. 그 중 속도면에서 딕셔너리를 이용한 조회가 가장 성능이 좋다.

문제 풀이

우선 enumerate 함수를 이용하여 인덱스와 값을 함께 꺼내주고 값을 key로 인덱스를 value로 하는 딕셔너리를 만든다.

그 후 타겟에서 첫 번째 수를 뺀 결과를 키로 조회한다. 딕셔너리의 경우 조회하는 것이 O(1)의 시간이 걸린다. 리스트에서 조회할때는 O(n)이 걸리므로 딕셔너리를 사용하는 것이 유리하다.

그러면 마찬가지로 enumerate 함수를 사용하여 인덱스와 값 모두 꺼낸 후 타겟에서 값을 뺀 것이 앞서 만든 딕셔너리에 포함되어 있는지를 확인한다.

def twoSum(self, 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]]

위의 코드에서 if의 조건으로 target-num in nums_map을 하였고 (O(1)의 시간이 걸린다.) num에 해당하는 i값이 nums_map[target-num] 자기자신과 같은지 확인하였다. 그 후 i와 target-num의 인덱스를 반환한다.

출처 : 파이썬 알고리즘 인터뷰 (박상길 지음)