TwoSum 문제를 풀면서 배우는 내가 짠 코드의 성능을 개선하는 과정!! (feat. 코딩 테스트)

https://youtu.be/cxhbgAbAiXI?si=Bj2dDUU__RCQ2Ews

문제 : 리스트에 있는 서로 다른 두 정수의 합이 target number와 같다면 true를 반환하는 함수를 구현하시오.

 

풀이1) 시간 복잡도는 n^2

def twoSum(nums, target);

    for i in range(len(nums)):
        for j in range(len(nums)):
            if i == j:
                continue
            if nums[i] + nums[j] == target:
                return True
    return False

 

풀이2) 시간 복잡도는 n^2 -> 풀이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 True
    return False

 

풀이3) 시간 복잡도는 n, Set을 활용하여 조회 성능 향상

def twoSum(nums, target);
    numbers = set(nums)
    for i in range(len(nums)):
        if (target - nums[i]) in numbers:
            return True
    return False

nums[i]와 target - nums[i]가 동일할 때 True로 잘못 판단될 여지가 존재

 

풀이4) 시간 복잡도는 n, 풀이3의 버그를 개선 & 빈 Set을 생성하여 n -> 1로 개선하여 성능이 향상됨

def twoSum(nums, target);
    numbers = set()
    for i in range(len(nums)):
        if (target - nums[i]) in numbers:
            return True
        else:
            numbers.add(nums[i])
    return False