출처
https://leetcode.com/problems/two-sum/description/
내용
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.
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.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
풀이 - 1
List와 target이 주어진다. List 와 target은 모두 integer이다.
List 안에 있는 두 개의 숫자의 합이 target과 동일해지는 숫자의 index를 출력하는 문제이다.
조건은 동일한 index의 숫자는 반복 사용할 수 없단 것이다.
제일 처음 떠오른 방법은 for문을 이용해서 list 안의 숫자들을 모두 매칭해보는 것이었다.
(이걸 영어로는 brute force라고 표현하더라)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)): # list 안의 숫자들을 순차적으로 돌린다
for j in range(i + 1, len(nums)): # 동일 index 반복을 하면 안되니 i+1부터 돌린다
if nums[j] == target - nums[i]: # target과 값을 비교한다
return [i, j] # index를 반환한다
Time complexity: O(n2).
바깥 루프 (for i in range(len(nums))): 이 루프는 n번 반복됩니다.
안쪽 루프 (for j in range(i + 1, len(nums))): 이 루프는 매번 n-i-1번 반복됩니다. 평균적으로 봤을 때, 대략 n/2번 정도 반복된다고 할 수 있어요.
따라서, 전체 반복 횟수는 n * (n/2)가 됩니다. 이를 간단하게 표현하면 약 n^2/2가 되는데, 빅오 표기법(Big-O Notation)에서는 상수를 무시하므로 **시간 복잡도는 O(n^2)**입니다.
Space complexity: O(1)
이 함수는 주어진 배열 nums와 몇 개의 변수(i, j 등)만 사용하고 있어요. 여기서 중요한 점은 추가적인 메모리 공간을 거의 사용하지 않는다는 점이에요. 리스트나 다른 데이터 구조를 새로 만들지 않으니까요.
따라서 이 함수의 공간 복잡도는 O(1)입니다.
풀이 - 2
첫번째 풀이는 Follow up question : "Can you come up with an algorithm that is less than O(n2) time complexity?"을 충족시키지 못한다.
이를 충족시키기 위해서는 Space complexity를 희생하여 hash map을 만들어준다.
Hash map은 {숫자 : index} 로 구성되고, target 에서 현재 숫자를 뺀 값이 hash map에 존재하는지 여부를 체크하여 없다면, 이번에 확인한 숫자와 index를 hash map에 저장한다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {} # 숫자 : index 형태의 dictionary
for i in range(len(nums)): # list의 루프를 돈다
complement = target - nums[i] # target에서 i번째 index의 숫자를 뺀다
if complement in hashmap: # 위의 값이 hashmap에 있다면, 목표달성
return [i, hashmap[complement]] # 이번 숫자의 index인 i와, 기존에 저장된 index를 출력한다
hashmap[nums[i]] = i # 위의 조건이 부합하지 않으면, i번째 숫자 (num[i])와 index (i)를 hashmap에 저장한다
Time complexity: O(n).
루프 (for i in range(len(nums))): 이 루프는 리스트 nums의 길이만큼 반복됩니다. 즉, n번 반복됩니다.
루프 내부에서는 다음과 같은 작업이 수행됩니다:
target - nums[i] 계산은 O(1) 시간 복잡도를 가집니다.
if complement in hashmap 체크도 일반적으로 O(1)입니다(해시맵에서 값을 찾는 시간은 평균적으로 상수 시간입니다).
hashmap[nums[i]] = i는 값을 해시맵에 저장하는 작업인데, 이것도 O(1) 시간 복잡도를 가집니다.
Space complexity: O(n)
해시맵에는 최대 n개의 키-값 쌍이 저장될 수 있습니다(nums 리스트의 모든 요소에 대해).
따라서 공간 복잡도는 해시맵에 저장되는 요소의 수에 비례하여 O(n)이 됩니다.