두 수의 합

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

ex) 입력 : nums = [2,7,11,15] , target = 9 --> 출력 : [0,1]

풀이1. 브루트 포스로 계산

• 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방식을 브루트 포스 방식이라고 합니다.

def twoSum(nums,target):
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i] + nums[j] == target:
                return [i,j]
                
                
twoSum([2,7,11,15],9)

[0,1]

코드해석

• for문을 2번 활용하여, 모든 케이스를 계산하는 방식입니다.
• 직관적으로 봤을 때 가장 이해하기 쉽고 구성하기 쉬운 코드지만, 효율성 부분에서 많이 부족한 코드입니다. 시간 복잡도가 O(n^2) 으로 지나치게 느린편입니다.

풀이2. in을 이용한 탐색

• 모든 조합을 계산해보지 않고 타겟에서 첫 번째 값을 뺀 값(target - n)이 존재하는지 찾는 방식입니다.

def twoSum(nums,target):
    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)
        
twoSum([2,7,11,15],9)

[0,1]

코드해석

• enumerate 함수는 리스트의 인덱스와 값들을 각각 매칭해주는 함수입니다. 즉, i에는 0,1,2... 순으로 배정되고 n에는 nums[0],nums[1],nums[2] 순으로 배정이 됩니다.
• 그러므로 target에서 nums의 원소들을 뺀 값이 하나씩 complement에 저장되고, 그때의 complement 값이 nums의 나머지 원소들 중에 있는지 in을 이용해 탐색하는 방식입니다.
• 이때의 시간복잡도는 O(n^2)이지만, in 함수는 O(n)으로 풀이1보다는 개선되었음을 알 수 있습니다.

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

• 풀이 2에서 조금 더 시간 복잡도를 개선하기 위한 형태입니다. 타겟에서 첫 번째 수를 뺀 결과를 키로 딕셔너리에서 조회하는 방법입니다.

def twoSum(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 nums.index(num), nums_map[target - num]


twoSum([2,7,11,15],9)

[0,1]

코드해석

• 딕셔너리를 생성한 후 , enumerate함수를 통해 키와 값을 거꾸로 딕셔너리에 저장했습니다. 그러므로, nums의 원소들은 key로 인덱스들은 value로 저장이 됩니다.
• 그 후, target - num 을 방금 생성한 딕셔너리에서 찾는지 점검을 하는 방식입니다. 이때 " i!= nums_map[ target - num ]" 을 넣는 이유는 첫번째로 target에서 뺀 값을 제외시키기 위함입니다. 즉, target이 num의 크기의 2배일때 본인이 결과로 리턴되는 것을 방지하기 위함입니다.
• 같은 형식의 for문이 사용되었으므로 다음과 같이 합칠 수 있습니다.

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

• 본인의 값을 딕셔너리에 넣기 전에 미리 딕셔너리에 target - num이 있는지 탐색했으므로 이전과 같은 중복 방지용 코드르 넣을 필요가 없습니다.

• 이와 같은 코드들을 작성하면 인덱스가 0인 원소와 1인 원소의 합이 타겟넘버라는 사실을 알 수 있습니다.