반응형
https://leetcode.com/problems/two-sum/description/
내 코드
# 시간복잡도 O(N^2)
class Solution(object):
def twoSum(self, nums, target):
result = []
for i in range(0, len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
result += [i, j]
return result# 시간복잡도 O(N)
class Solution(object):
def twoSum(self, nums, target):
hash_table = {} # 해시 테이블 -> 딕셔너리
for i, num in enumerate(nums):
complement = target - num # '짝' 값 계산
if complement in hash_table: # 짝 값이 해시 테이블에 있다면, 쌍을 찾음
return [hash_table[complement], i]
hash_table[num] = i # 현재 값과 인덱스를 해시 테이블에 저장
return [] # 여기는 실제로는 도달하지 않아요, 해답이 항상 존재한다고 가정 했기 때문.Review
난이도는 쉬운? 문제였습니다.
하지만
시간 복잡도를 줄이라고 무언의 압박을 받았네요
^^_^^
2중 for 문으로 모든 경우의 수를 계산해서 알맞은 i, j 값으로 처음에 해결했었는데요
시간 복잡도를 줄이기 위해서 해시테이블 자료구조<딕셔너리>를 사용했습니다.
문제를 보면 one solution 만 있다고 가정을 했기 때문에
target과 짝을 이루는 쌍이 하나 있을 거예요!
주석으로는 이해가 안 될 수 있으니 그림으로도 설명하겠습니다.
예제 nums = [3, 2, 4], target = 6 으로 설명할게요.
이렇게 for문 하나로 O(N)의 시간복잡도로 해결을 할 수 있어요!
문제에 나와있듯이, 하나의 해결책 만 찾을때 용이합니다.
질문이나 지적할 사항 있으면 언제든지 의견 주세요
（ •́ .̫ •̀ ）
반응형