[python] LeetCode 1번: Two Sum(easy)
![[python] LeetCode 1번: Two Sum(easy)](/assets/img/leetcode.jpeg)
Problem
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Constraints:
2 <= nums.length <= 105
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
정수형 배열인 nums와 정수 target이 주어졌을 때, 더해졌을 때 target이 되는 두 원소의 인덱스를 구하여라.
각각의 인풋값은 오직 하나의 해답만을 가지며 같은 원소를 두 번 사용할 수 없다고 가정한다.
인덱스 순서 상관 없이 결과를 반환해도 된다.
문제 링크 : 리트코드 1번
<Try>
가장 먼저 생각할 수 있는 방법은 가능한 모든 경우의 수를 대입하여 답을 찾는 brute force 방식이다.
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)):
if nums[i] + nums[j] == target:
return [i, j]
하지만 제출 해보면 Time Limit Exceed 라고 나온다…
효율적인 코드를 짜기 위해선 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 고려해야 한다. 당연히 시간 복잡도와 공간 복잡도가 동시에 낮을수록 좋겠지만 일반적으로 이 둘의 관계는 Trade-off 관계이다. 그리고 알고리즘 문제는 둘 중 시간 복잡도를 낮추는 방향을 원한다.
위 코드의 경우 최대 n(n-1)/2 번의 검사를 해야 하므로 시간 복잡도는 O(n2) 이다.
<Solution>
이번에는 시간 복잡도를 낮추기 위해서 Dictionary를 이용할 것이다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {} # {value : index}
for i, v in enumerate(nums):
if target - v not in dict:
dict[v] = i
else:
return [dict[target-v], i]
이 코드는 nums 배열을 한 번만 순회하면서 해당 순서에 있는 값을 dict에 hashmap의 형태로 저장한다. 그리고 현재 값 v와 dict에 저장된 값들 중 합이 target이 되는지 검사한다.
즉, v + ? = target 이 되는 ? 값이 dict에 저장되어 있는지 확인하면 되므로 target - v 값을 검사한다.
코드 제출 결과 통과 하였다.
이 코드의 경우 최대 nums 배열을 한 번 순회 하므로 시간 복잡도는 O(n)이다.
cf) 파이썬 Dictionary에서 특정 key값을 찾을 때, keys() 배열 전체를 다 뒤져서 찾는 것이 아니라 바로 찾을 수 있다. 이러한 원리로 앞선 방법에 비해 시간 복잡도가 O(n2)에서 O(n)으로 감소하 였다. 파이썬의 Dictionary는 java나 c언어의 HashMap에 해당된다.
