두 수의 합 문제

 

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

 

target 을 보고 nums 라는 리스트에 들어있는 원소 중 두 개를 더하여 target 이 될 수 있는 인덱스를 리턴하는 문제이다.

 

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

브루트 포스(Brute-Force) 방식은 이 배열을 2번 반복하면서 즉, for 문을 두 번 돌려서 모든 가능한 두 쌍을 꾸리는 단순한 방식이다.

아래처럼 두번의 for 문 반복으로 인덱스를 출력할 수 있게 쉽게 작성할 수 있다.

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

 

풀이 2) in을 이용한 탐색

모든 조합을 비교하지 않고, target 에서 첫번째 값을 뺀 값을 target - n 이라고 하면 그 수가 있는지를 in 함수를 통해서 리스트를 죽 훑는다. 앞의 브루트 포스 계산과 별다른 차이는 없다. 왜냐하면 in 함수도 역시나 한번 죽 훑는 작업을 하기 때문이다. in 함수가 내부적으로 빠른 코드로 되어 있어 그렇다.

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(0,len(nums)-1):
            t_n = target - nums[i]
            if t_n in nums[i+1:]:
                return (i, nums[i+1:].index(t_n) + (i+1))
                

 

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

딕셔너리에 값과 인덱스를 key, value 로 놓고 조회해서 target - num 과 맞는게 있는지 확인하고 있으면 자기자신을 제외하고 value 인 인덱스를 출력하게 한다.

    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]]

 

풀이 4) 조회 구조 개선

 

풀이 3번은 딕셔너리 만들어 놓고 했는데, 이번 풀이는 만들어 가면서 조회하는 방법이다. 속도의 차이는 그렇게 없었다.

 

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(0,len(nums)):
            t_n = target - nums[i]
            if t_n in nums[i+1:]:
                return (i, nums[i+1:].index(t_n) + (i+1))

 

만약 nums 가 정렬되어 주어진다면 투 포인터 방법을 사용할 수도 있다. 양쪽에 포인터를 하나씩 두고, 더하면서 target 보다 크면 오른쪽에 포인터를 왼쪽으로 한칸씩 이동하고 다시 더하고, target 보다 작으면 왼쪽 포인터를 오른쪽으로 옮기는 식으로 말이다. 정렬이 되지 않은 input 을 받기 때문에 여기선 사용 불가이다.