[python] 1. Two Sum

 

Two Sum - LeetCode

Two Sum - LeetCode

두 수의 합 

 

더하여 target의 값이 되는 두 값의 인덱스를 반환하는 문제 

매우 쉬운 문제이나 여러 가지 방법으로 풀이할 수 있어 코딩 인터뷰에서 높은 빈도로 출제되는 문제이다.

 

풀이 

다양한 방법으로 풀이가 가능한 문제이다. 

 

브루트 포스로 풀이

 

브루트 포스 (brute-force): 무차별 대입 방식 

모든 조합을 다 더해서 일일이 확인해본다면 브루트 포스 방식을 사용한 것 

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:        
        for i in range(len(nums) -1):
            for j in range(i + 1, len(nums)):
            # 모든 조합을 돌아가며 
            # 합이 target 과 일치하는지 확인 
                if nums[i] + nums [j] == target:
                    return [i, j]

시간 복잡도가 O(n^2)로 비효율적인 풀이 방법이다.

또한, 지나치게 느리다. 

그러므로 브루트 포스 방식으로 문제를 푼다면 타임아웃에 주의해야 한다. 

 

in 을 이용한 풀이 

 

target에서 배열의 값을 뺀 값이 존재하는지 in을 사용하여 탐색하는 풀이 방법 

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
            for i, n in enumerate(nums):
            # target 에서 n 을 뺀 값을 complement 로 잡는다 
            complement = target - n
            # 자기 자신의 인덱스를 포함하지 않도록 하기 위해 인덱싱 연산 
            if complement in nums[i+1:]:
                # nums[i+1:].index(complement) 을 사용하면 
                # num[i+1:] 으로 슬라이싱 해서 인덱스를 찾게된다 
                # 그래서 원래의 자리를 찾고 싶다면 (i+1)을 해주는 것이 좋다 
                return i, nums[i+1:].index(complement) + (i+1)

브루트 포스를 사용한 방식과 시간 복잡도는 동일하지만 

python에서 in 연산이 훨씬 빠르고 가볍기에 훨씬 빠르게 실행된다. 

 

첫 번째 수를 뺀 결과 키 조회

 

위의 방식에서 시간 복잡도를 개선한 방식 

dict을 사용하여 인덱스 값을 찾는다.

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    	# input 된 배열의 인덱스와 값의 위치를 바꾸어 저장할 dict 
    	nums_map = {}
        for i, num in enumerate(nums):
        	# key-value 의 위치를 뒤집는다. 
            # 이 방법을 사용하면 인덱스를 좀 더 쉽게 찾을 수 있다.
            nums_map[num] = i

        for i, num in enumerate(nums):
        	# target - num 이 nums_map 에 있고 인덱스가 겹치지 않는다면 
            if target - num in nums_map and i != nums_map[target-num]:
            	# num 의 인덱스 값과 target-num 의 인덱스 값을 반환한다. 
                return [i, nums_map[target-num]]

조회가 평균적으로 O(1)에 가능하다 

앞선 방법들에 비해 훨씬 빠른 실행 속도를 보인다. 

 

조회 구조 개선

 

두 개의 for 문을 하나로 합쳐 코드 작성 

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target-num],i]
            nums_map[num] = i

실행 시간의 큰 차이는 없지만 코드가 더 간결해졌다. 

 

투 포인터 이용 

 

왼쪽 포인터의 값과 오른쪽 포인터의 값의 합이 타깃보다 

크다면 -> 오른쪽 포인터를 왼쪽으로 

작다면 -> 왼쪽 포인터를 오른쪽으로 

이동시키며 값을 조정하는 방식 

 

그러나 이 방식은 사용할 수 없다! 

1. 투 포인터를 사용하여 이 문제를 해결하려면 정렬이 필요하다 

2. 정렬을 하면 인덱스가 엉망이 되어 문제를 풀 수 없어진다. 

from typing import List
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 1. 정렬이 반드시 필요 
        nums.sort()
        # 2. 그러나 정렬하면 인덱스가 엉망이 된다 
        # 값만을 구하는 문제라면 사용 가능 
        left, right = 0, len(nums)-1
        # 두 포인터의 위치가 같아지면 멈춘다 
        while not left == right:
        	# 합이 target 보다 작으면 왼쪽 포인터를 오른쪽으로 이동 
            if nums[left] + nums[right] < target:
                left += 1
            # 합이 target 보다 크면 오른쪽 포인터를 왼쪽으로 이동 
            elif nums[left] + nums[right] > target:
                right -= 1
            # 두 포인터가 가리키는 값의 합과 target 의 값이 같다면 반환 
            else:
                return [left, right]