본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.
양의 정수 배열 nums와 정수 target이 주어집니다,
더했을때 target이 되는 배열의 두 숫자의 인덱스를 배열로 만들어 리턴하세요.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
2와 7을 더하면 target인 9가 된다, 그렇기에 2와 9의 인덱스인 0과 1을 배열로 감싸 리턴했다.
모든 숫자쌍의 경우를 전부 확인하는 것.
시간 복잡도는 O(n^2) 이고 공간복잡도는 O(1) 이다.
def twoSum(numbers, target):
for i in range(len(numbers)):
for j in range(i+1, len(numbers)):
if numbers[i] + numbers[j] == target:
return [i, j]
우리가 알아야 하는것은 두 숫자를 더했을때 특정 숫자가 되도록 하는것을 찾는것이다.
두 숫자가 A와 B이고 찾아야 하는 숫자가 T일때 A + B = T 가 성립시 B = T - A도 성립한다.
즉 A에 맞는 B라는 숫자는 T - A라는 값이 되어야 한다는 것이다.
이를 위 문제에 적용시, 첫번째 2라는 숫자에 target이 9이기 때문에 뒤에 나오는 숫자들 중 9가 있냐 없냐를 확인할수 있다면 될것이다.
이를 위해 MAP, 파이썬의 dictionary를 이용해 필요한 숫자들을 미리 적어둬 O(1)의 시간복잡도로 해결할수 있다.
이를 위한 코드는 다음과 같다.
def twoSum(numbers, target):
d = dict()
for i in range(len(numbers)):
# 자기 자신이 앞에 있었던 숫자들중 필요한 숫자였을 경우, 리턴.
if numbers[i] in d:
return [d[numbers[i]], i]
# 그렇지 않다면 dictionary에 자기 자신과 더해졌을때 target이 되는 숫자를 찾기위해 등록.
else:
d[target - numbers[i]] = i
시간복잡도는 O(n)이 되며, 공간복잡도는 dict를 사용하기에 O(n)이 된다.