two-sum [leetcode 1]
https://leetcode.com/problems/two-sum
리트코드 첫번째 문제이다.
첫번째 문제답게 난이도는 낮은편이고 그럼 문제를 살펴보도록 하자.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
입력으로 nums 리스트가 주어지고, 리스트 안에 숫자가 있는데 이 조합을 통해 target을 만드는 문제다.
제약조건을 살펴봐야하는데 리스트의 크기는 2 ~ 104 사이의 크기를 가지고 있고 오직 답은 1개만 나온다고 한다.
그래서 결국 최종적으로 리턴해야할 값은 리스트형태의 nums의 인덱스 위치다.
문제를 딱 보면 완전탐색(브루트포스) 형태로 모든것을 검색하면서 탐색할 수 있을거라 생각이 나서 바로 풀어봤다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]
0 1 2 3 이라는 인덱스가 있을때
0 1 -> 0 2 -> 0 3
1 2 -> 1 3
2 3
순서로 리스트를 순회하면서 확인하는 코드이다.
사실 보면 시간복잡도가 O^2이므로 속도면에서는 빠르지 않다.. 정확하게는 (0.5n^2) 정도가 되겠지만;
Dict 형태를 활용한다면 O(n)으로 시간복잡도를 줄일 수 있다.
실제로 실행해보면 가장 빠르게 동작할 수 있는 것을 확인해볼 수 있다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_dict = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_dict:
return [num_dict[complement], i]
num_dict[num] = i
return [] # 해답이 없는 경우 (문제 조건에 따르면 이 경우는 발생하지 않습니다)
간단하게 코드를 리뷰해보면
1. num_dict 빈 딕셔너를 생성하고
2. enumerate를 통해 num 인덱스 i를 가져오게 된다.
3. 현재 숫자 num와 합쳐 target이 될 수 있는 값을 complement로 계산한다.
4. complement 값이 num_dict 딕셔너리 안에 있는지 확인하고, 있다면 어떤 숫자와 현재 숫자가 합쳐져서 target이 될 수 있는 것을 의미한다.
5. 결국 complement가 num_dict에 있다면 complement 숫자의 인덱스와 현재 숫자의 인덱스를 반환하며 이게 return 된다.
ref