덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.
처음 이 문제를 접하게 되면, 모든 경우의 수에 대한 조사를 할 것이다. 나 또한 그렇게 해결하였지만 이는 n의 제곱의 경우의 수로 매우 비효율 적이다. 그래서 파이썬으로 이러한 최적화 문제를 풀 때 가장 유용한 것은 딕셔너리를 이용하는 것이다.
예를들어 [2,3,7] 에서 3이라는 값이나 인덱스를 찾으려면 in이나 index 함수를 사용하여야 하는데 이는 O(n)이다. 하지만 이를 딕셔너리로 변환하여 'Dict[값] = 인덱스' 형태로 저장하면 해당 값의 인덱스를 찾거나, 해당 값이 있는지 확인하는데 걸리는 시간은 O(1)이 된다.
이를 활용하여 이 문제를 해결해보자.
먼저, 딕셔너리 형태로 배열을 정리한다.
num_dict = {}
for i, n in enumerate(nums):
num_dict[n] = i
보는 것과 같이 'Dict[값] = 인덱스' 형태로 딕셔너리를 생성하였다.
그 다음, 'target - 값' 이 딕셔너리에 존재하는 지를 확인하면 덧셈하여 만들 수 있는 배열의 두 숫자가 될 것이다.
for i, n in enumerate(nums):
if num_dict.get(target - n) != None and i != num_dict[target - n]:
return i, num_dict[target-n]
여기서 i != num_dict[target-n]을 확인하는 이유는, 같은 인덱스에 있는 값을 2번 사용 할 수도 있기 때문에 그것에 대한 예외를 설정해 주는 것이다.
전체 코드는 다음과 같다.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_dict = {}
for i, n in enumerate(nums):
num_dict[n] = i
for i, n in enumerate(nums):
if num_dict.get(target - n) != None and i != num_dict[target - n]:
return i, num_dict[target-n]
'코딩테스트 > 알고리즘' 카테고리의 다른 글
[Q. 09] 세 수의 합 (0) | 2023.03.20 |
---|---|
[Q. 08] 빗물 트래핑 (0) | 2023.03.20 |
[Q. 06] 가장 긴 팰린드롬 부분 문자열 (0) | 2023.03.16 |
[Q. 05] 그룹 애너그램 (0) | 2023.03.16 |
[Q. 04] 가장 흔한 단어 (0) | 2023.03.15 |