[LeetCode] #015 Three Sum - Improve speed
이번 포스트에서는 지난번에 구현한 3Sum의 속도를 개선시킨 알고리즘을 설명한다.
알고리즘 설명은 이 링크에서 확인할 수 있다.
먼저 의사코드를 작성하면 아래와 같다.
입력받은 요소 = [-4, -3, -2, 1, 0, 1, 2, 2, 3]
0. 리턴받을 리스트를 생성한다.
1. 입력받은 요소를 오름차순정렬한다.
2. 입력받은 요소들을 검색사전으로 만들기위해 해쉬맵을 생성한다.
3. 해쉬맵의 키에 입력받은 요소들을 담고 값에는 중복되는 값을 카운트한다.
ex [-2,-1,0,0]:) hashmap[-2] = 1, hashmap[-1] = 1, hashmap[0] = 2
3. 검색사전의 키값중 0의 값이 2개 이상이라면 리스트에 [0,0,0]을 추가한다.
4. 검색사전으로 음수 집합 리스트를 생성한다.
5. 검색사전으로 양수 집합 리스트를 생성한다.
6. 음수 집합 리스트를 순환한다.
7. 양수 집합 리스트를 순환한다.
8. 음수요소와 양수요소를 더한 값을 합계에 설정하고 부호를 반전시킨다.
9. 검색사전에 합계가 존재하지 않으면 루프를 건너뛴다.
10. 다음 경우에 수에 해당하는 리스트를 추가한다.
[음의요소, 합계, 양의요소] 합계가 0인 경우
[합계, 음의요소, 양의요소] 합계가 음의요소보다 작을경우
[음의요소, 양의요소, 합계] 합계가 양의요소보다 클경우
[음의요소, 음의요소, 양의요소] 합계가 음의요소와 같고 요소가 1개이상인경우
[양의요소, 양의요소, 음의요소] 합계가 양의요소와 같고 요소가 1개 이상인경우
11. 리스트를 반환한다.
코드로 구현하기 (파이썬)
class Solution:
def threeSum(self, nums):
res = []
nums.sort()
lookup = dict()
for num in nums:
if num in lookup: lookup[num] += 1
else: lookup[num] = 1
if 0 in lookup and lookup[0] > 2: res.append([0,0,0])
neg = [n for n in lookup if n < 0]
pos = [n for n in lookup if n > 0]
for n in neg:
for p in pos:
sum = -p - n
if sum not in lookup: continue
if sum == 0: res.append([n,sum,p])
elif sum < n: res.append([sum,n,p])
elif sum > p: res.append([n,p,sum])
elif sum == n and lookup[sum] > 1: res.append([n,n,p])
elif sum == p and lookup[sum] > 1: res.append([n,p,p])
return res
이 알고리즘의 경우또한 O(n^2)로 시간복잡도가 전과 같지만 이미 계산된 결과값을 해시테이블에서 찾기때문에 속도가 빠르다. 실행시켜보면 313개의 테스트를 통과하고 런타임시간이 320 ms로 전보다 약 5배정도 빨라진 것을 확인 할 수 있다.