출처
: LeetCode
문제
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.
(생략)
나의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
size_nums = len(nums)
solved = []
for i in range(size_nums):
for j in range(i+1, size_nums):
temp_left = nums[i]
temp_right = nums[j]
if (temp_left + temp_right == target):
solved.append(i)
solved.append(j)
return solved
시간복잡도로 $O(N)$이나 이에 가까운 걸 고민했지만
역시 생각나지 않았고, 결국 이중 for문으로 했다.
당연히 실행시간 면에선 하위 75프로…
아래는 리트코드에서 제시한 해시 테이블 풀이이다.
이거 꼭 배워가야겠다.
리트코드 제시 풀이
1
2
3
4
5
6
7
8
9
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
hashmap[nums[i]] = i
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap and hashmap[complement] != i:
return [i, hashmap[complement]]
(출처: LeetCode solution)
1
2
3
4
5
6
7
8
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap:
return [i, hashmap[complement]]
hashmap[nums[i]] = i
(출처: LeetCode solution)
enumerate
이 참에,
해시 풀이에 쓰인 enumerate에 대해 알아보자
1
enumerate(iterable, start=0)
말 그대로,
열거 가능한Enumerate 객체를 반환한다.
인자 중에서
iterable은 시퀀스Sequence 자료형이거나
iterator, 또는 이터레이션Iteration을 지원하는 객체여야 한다.
start를 통해서는
시작 카운트 숫자를 지정할 수 있다.
1
2
for i in enumerate([1, 2, 3, 4, 5], start=10):
print(i)
위의 코드의 결과는 다음과 같다.
1
2
3
4
5
(10, 1)
(11, 2)
(12, 3)
(13, 4)
(14, 5)