[알고리즘]두 수의 합

2021.10.19 04:13

안녕하세요

프로그래밍을 배우는 빛나는 샤트입니다.

 

[Python Algorithm Study]

*아래 내용은 파이썬 알고리즘 인터뷰 라는 서적을 공부하면 정리한 내용입니다.

 

두 수의 합

• 목표: 입력된 list의 인자 중 덧셈하여 target을 만들 수 있는 배열의 두 숫자 인덱스를 return
• 입력: [2,7,11,15]
• 타겟: 9
• 출력: [0,1]
• 문제 링크(LeetCode) two-sum

 

1. 풀이1 브루터 포스(배열을 2번 반복하면서 모든 조합을 더해 일일히 확인해보는 무차별 대입 방식)

# 풀이1 브루트 포스(Brute Force)
# 배열을 2번 반복하면서 모든 조합을 더해 일일이 확인해보는 무차별 대입 방식
# 시간 복잡도 O(n^2)

def twoSum_BruteForce(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_BruteForce(nums, target)) # [0,1]

 

2. 풀이2 in을 이용한 탐색

# 풀이2 in을 이용한 탐색
# 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색
# 전체 시간 복잡도는 O(n^2)이지만 같은 시간 복잡도라도 in 연산쪽이 훨씬 더 가볍고 빠르다.

def twoSum_in(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_in(nums, target)) # [0,1]

 

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

# 풀이3 첫 번째 수를 뺀 결과 키 조회
# 첫 번째 수를 빼면 두 번째 수를 바로 알 수 있다.
# 두 번째 수를 key로 하고 기존의 인덱스를 value인 딕셔너리를 생성
# 시간복잡도 O(n)

def twoSum_dict(nums:list, target:int) -> list:
    nums_map = {}
    # key, value를 바궈서 딕셔너리로 저장
    for i, num in enumerate(nums):
        nums_map[num] = i

    # 타겟에서 첫 번째 수를 뺀 결과를 key로 조회
    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]]

print(twoSum_dict(nums, target)) # [0,1]

 

4. 풀이4 조회 구조 개선

# 풀이4 조회 구조 개선
# 하나의 for문 안에서 해결
# 시간복잡도 O(n)

def twoSum_dict_one_for_loop(nums:list, target:int) -> list:
    nums_map = {}

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

print(twoSum_dict_one_for_loop(nums, target)) # [0,1]

 

5. 풀이5 투 포인터 이용

(정렬 필수. 만약 인덱스를 물어보면서 정렬이 되어 있지 않는 배열에는 사용할 수 없음)

# 풀이5 투 포인터 이용
# 정렬이 되어 있다는 가정하에 사용해야함
# 인덱스를 물어보면서 정렬이 되어 있지 않는 배열에는 사용할 수 없음
# 초기에는 맨 왼쪽, 맨 오른쪽인자부터 덧셈을 하면서 덧셈결과가 타겟보다 크면 오른쪽 포인트를 왼쪽으로
# 반대로 덧셈결과가 타겟보다 작다면 왼쪽 포인터를 오른쪽으로 이동
# 시간복잡도 O(n)

def twoSum_TwoPoint(nums:list, target:int) -> list:
    left, right = 0, len(nums)-1
    while left != right:
        # 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
        if nums[left] + nums[right] < target:
            left+=1
        elif nums[left] + nums[right] > target:
            right-=1
        else:
            return [left,right]

print(twoSum_TwoPoint(nums,target)) # [0,1]

 

 

여러분의 빛나는 코딩을 응원하며

샤트