[LeetCode] #001 Two Sum
LeetCode 에서 Three Sum 문제를 해결하기 위해서는 Two Sum을 구현할 줄 알아야하므로
Two Sum을 구현해보려한다.
https://leetcode.com/problems/two-sum/solution/
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice
Example :
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
먼저 주어진 정수배열에서 두 값의 합이 찾고자 하는 값일 경우 두 인덱스들의 요소를 리턴하면 되는데
동일한 요소는 한번만 사용해야한다.
먼저 단순하게 생각해 보면 각 요소를 n번 반복하면서 (target값 - x) 과 같다면 요소를 리턴하는
코드를 작성해 볼 수 있다.
def twoSum(self, nums, target):
for x in range(len(nums)):
for y in range(len(nums)):
if nums[y] == target - nums[x]:
return [x, y]
return []
이때 시간복잡도는 O(n^2) 이므로 효율이 떨어지는 알고리즘이라 할 수있다.
배열을 처음부터 끝까지 다 찾아야하는 이 알고리즘을 개선하기 위해서는
O(1)공간과 O(n)시간을 교환하는 알고리즘을 사용할 수 있다.
즉 중복이 배제된 요소가 배열의 키로 들어가 있다면 시간복잡도 : O(n)으로 훨씬더 빠르게 찾을 수 있다.
이런 알고리즘에 최적화 된 것은 바로 해시테이블이다.
먼저 코딩할 알고리즘을 풀어보면 아래와 같다.
1. 먼저 해시테이블을 생성하고
2. 검색테이블을 순회하면서
3. 만약 해시테이블에 검색키가 존재한다면 배열[x,y]를 리턴하고
4. 그렇지 않으면 해시테이블의 키에 [target-배열의 요소값]로 하고 값을 요소의 키값으로 넣는다.
이제 파이썬으로 구현해보자.
class Solution:
def twoSum(self, nums, target):
hashmap = {}
for index, item in enumerate(nums):
if item in hashmap:
return [hashmap[item], index]
else:
hashmap[target - item] = index
return []
이제 프로그램을 실행시켜 보면 시간복잡도 O(n)으로 개선시킨 결과값을 볼 수 있다.
solution = Solution()
print(solution.twoSum([2, 5, 7, 15], 9))
[0, 2]
Process finished with exit code 0