[파이썬 알고리즘 인터뷰] 배열 - 두 수의 합

🐍 문제

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

• 입력
  nums = [2, 7, 11, 15], target = 9
• 출력
  [0, 1]

🐍 내 풀이1 - 모든 숫자 전부 확인

가장 간단하게 주어진 리스트의 값을 모두 확인하였다.

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

for i in range(len(nums) - 1):
	for j in range(i + 1, len(nums) - 1):
		if nums[i] + nums[j] == target:
			output_list.append(i)
			output_list.append(j)

print(output_list)

🐍 내 풀이2 - 덧셈 속성 이용하여 일부 값만 확인

덧셈을 하여 값을 찾는다는 것은 최소 결과로 나와야하는 값보다 같거나 작은수 두 개가 필요하다. 주어진 리스트를 정렬하여 target으로 주어진 값보다 같거나 작은 값만 비교한다. 출력값이 처음에 주어진 숫자 리스트의 인덱스값이므로 다시 해당하는 값의 인덱스를 찾는 과정이 필요하다.

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

def get_multiple_list(nums, target):
    output_list = []

    if not nums:
        return output_list
    elif len(nums) == 1:
        return output_list
    elif len(nums) == 2:
        return [0, 1]

    nums_sorted = sorted(nums)

    for i in range(len(nums_sorted) - 1):
        if nums_sorted[i] > target:
            break

        for j in range(i + 1, len(nums_sorted) - 1):
            if nums_sorted[j] > target:
                break
            
            if nums_sorted[i] + nums_sorted[j] == target:
                output_list.append(nums.index(nums_sorted[i]))
                output_list.append(nums.index(nums_sorted[j]))
                break

    return output_list

print(get_multiple_list(nums, target))

🐍 교재 풀이1 - 브루트 포스로 계산

내 풀이 1번과 같이 모든 값을 반복문을 통해 계산하여 확인하는 방법이 브루트 포스 방법이다. 교재 풀이를 봤을 때 값이 없는 경우는 따로 처리하지 않는 것으로 보아 실제 리트코드에 있는 문제에 값이 없는 경우는 없는듯하다.

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

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

print(twoSum(nums, target))

🐍 교재 풀이2 - in을 이용한 탐색

주어진 리스트를 앞에서부터 확인하여 목표 숫자에서 현재 숫자를 뺀 후 나와야 하는 값이 리스트에 있는지 확인한다. 리스트에서 값의 존재를 확인하는 in 연산도 for문과 마찬가지로 시간복잡도 O(n)을 가지지만 실제로 실행되는 시간은 for문보다 in 연산이 더 빠르다. 교재에서 비교했을 때 교재 풀이 1번은 5,284밀리초가 걸렸다면 교재 풀이 2번은 864밀리초가 걸렸다. 값의 존재 유무를 찾는다면 for문보다는 in 연산을 이용하자.

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

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

print(twoSum(nums, target))

🐍 교재 풀이3 - 첫 번째 수를 뺀 결과 키 조회

교재 풀이2와 비슷하게 target에서 현재 숫자를 뺀 값을 찾는 방법은 동일하다. 다만 주어진 리스트를 미리 딕셔너리로 변환하여 찾아야 하는 값의 인덱스 값을 찾을 때의 시간을 줄였다.

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

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

print(twoSum(nums, target))