위코드 코드카타 Week1 Day1 - 배열에서 합하면 sum이 되는 두 숫자 반환

문제

리스트(nums)와 '특정 수(target)'를 인자로 넘기면, 더해서 '특정 수'가 나오는 index를 배열에 담아 반환하라.

target이 되는 조합은 배열 전체 중에 2개 밖에 없다고 가정한다.

예를 들어 two_sum([4, 9, 11, 14], 13)는 [0, 1]을 반환함.

 

내가 해결한 방식

시간 복잡도 : O(n), 공간 복잡도 : O(n)

1) 해시 테이블로 사용할 배열 h 생성. h의 크기는 nums에서 제일 큰 값 + 1이고 디폴트 값은 모두 -1.

2) for문으로 nums 배열 요소 하나씩 살펴봄

   - 검사한 nums 요소 elem을 h의 인덱스로 사용 : h[elem]에 인덱스값 저장

   - target이 a보다 크면 h[target - a]확인, 작으면 h[a - target] 확인

   - h[target - a] 또는 h[a - target] 값이 -1이 아니면 짝이 있다는 뜻 :  값 반환

 

=> 통과했지만 

- nums에서 제일 큰 값이 정말 큰 경우, 배열 h 크기가 너무 커짐

- 가독성 떨어짐

def two_sum(nums, target):
  max_num = max(nums) + 1
  # 디폴트 값을 -1로 세팅한 배열 h를 만든다.  
  h = [-1] * (max_num)

  for i in range(len(nums)):
    # 확인한 숫자는 h[nums[i]]에 인덱스를 저장한다.  
    elem = nums[i]
    h[elem] = i

    # target이 nums[i]보다 작은 경우 h에 nums[i] - target이 있는지 확인
    # 짝이 있는 경우 배열 반환, 없는 경우 넘어감
    if target < elem:
        if h[elem - target] != -1:
            return [i , h[elem - target]]

    # target이 nums[i]보다 큰 경우 h에 target - nums[i]이 있는지 확인
    # 짝이 있는 경우 배열 반환, 없는 경우 넘어감
    elif target > elem:
        # 짝이 있는 경우 배열 반환
        if h[target - elem] != -1:
            return [h[target - elem],i]

  # 짝이 없으면 빈 배열 반환
  return []

 

더 나은 방식 (GeeksForGeeks 참조)

1) 배열이 아니라 딕셔너리를 해시테이블로 사용

2) for문으로 nums 배열 요소 하나씩 살펴봄

   - 딕셔너리 h에 찾을 숫자(target - nums[i])로 된 키가 존재하는지 확인

   - 있으면 [해당 키의 값, i] 반환

   - 없으면 키가 nums[i]이고 값이 i인 쌍을 h에 저장

def two_sum(nums, target):
    # 새 딕셔너리 생성
    h = {}
    
    for i in range(len(nums)):
        # 찾아야 하는 숫자를 numerToFind에 저장
        currentNumber = nums[i]
        numberToFind = target - currentNumber

        # h에 키가 numberToFind인 요소가 있으면 [해당 키의 값, i] 반환
        if (numberToFind in h):
            return [h[numberToFind], i]
        
        # h에 키가 numberToFind인 요소가 없으면 h에 '키 현재숫자: 값 인덱스' 쌍 저장     
        h[currentNumber] = i
    return []