Week 2-1. [Hash Table] 1. Two Sum (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150 

Two Sum - LeetCode

정수 배열 중 두 숫자의 합이 target이 되는 두 수의 인덱스를 리스트로 반환하라.

• 유효한 답은 하나만 존재한다.
• 리스트 내부 순서는 상관없다.
• | nums | ∈ [2, 10^4]

 

🔎 어떤 식으로 접근했는가?

Two pointer를 사용하기 위해 정렬을 해야 한다.

마지막에 인덱스를 반환해야 하기 때문에 미리 튜플 형태로 값과 인덱스를 함께 담아 놓는다.

그 후 배열을 정렬한뒤 lp와 rp를 이용해 합이 target이 되는 두 원소를 찾는다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

nums의 길이가 최대 10^4이기 때문에 2중 for문으로 완전 탐색하면 시간 복잡도 효율이 굉장히 낮아진다.

Two pointer를 이용했다.

 

📝 의사 코드

lst = nums의 (값, 인덱스)를 복사한 리스트
lst.sort()

lp, rp = 0, 마지막 인덱스
while lp < rp:
	if lst[lp][0]와 lst[rp][0]의 합이 target과 같다면:
    	return [lst[lp][1], lst[rp][1]]
    elif target 보다 작다면:
    	lp 한 칸 늘리기
    else:
    	rp 한 칸 줄이기

 

🎯 구현 코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        lst = [(val, idx) for idx, val in enumerate(nums)]
        lst.sort(key=lambda x:x[0])

        lp, rp = 0, len(nums) - 1
        while lp < rp:
            if lst[lp][0] + lst[rp][0] == target:
                return [lst[lp][1], lst[rp][1]] # 원래 인덱스 반환
            elif lst[lp][0] + lst[rp][0] < target:
                lp += 1
            else:
                rp -= 1

        return []

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

lst.sort()의 시간복잡도는 O(n log n)이다. Two pointer를 이용해 두 수의 합을 계산할 때의 시간복잡도는 O(n)이다.

따라서 전체 코드의 시간 복잡도는 O(n log n)이다.

 

✍️ 성능 회고

1초의 시간 제한을 갖는다고 할 때, O(n log n)의 시간 복잡도를 가진 코드에서 입력의 최대 크기 n은 대략 10^5이다.

문제에서 입력의 최대 크기는 10^4이므로 안정적으로 처리할 수 있다.

 

💡 무엇을/어떻게 개선할 수 있을까?

Hash Table 문제인 만큼 Hash Table을 이용하여 개선할 수 있을 것 같다.

Hash Table을 어떻게 활용해야할지 모르겠어서 우선 Two Pointer로 풀었다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

해시 테이블(파이썬에서는 딕셔너리)에 값과 인덱스를 담아두고,

nums를 순회하며 보수(target-nums[i])를 구한다.

 

보수가 해시 테이블 안에 있으면서 인덱스가 i와 다르다면 정답이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = dict()

        for i, x in enumerate(nums):
            dic[x] = i # (key, value): (값, 인덱스)

        for i in range(len(nums)):
            comp = target - nums[i] # complement: 보수
            if comp in dic and dic[comp] != i: # 해시 테이블에 보수가 있고 인덱스가 다르면 찾은 것
                return [i, dic[comp]]
        
        return []

+) 참고로 보수란..

⏱ 성능 측정 (시간복잡도/공간복잡도)

O(n)의 시간 복잡도를 갖는다.

 

느낀 점

정렬 없이 linear search만으로 효율적으로 해결할 수 있는 문제였다.

해시테이블을 이런식으로 활용할 수 있다는 것이 새로웠다.

 

참고 자료

Leetcode 1 Two Sum - twopointer sliding window method