[TIL] 리트코드 - Two Sum 다르게 풀기 : 정렬과 이진 탐색

https://daelkdev.tistory.com/29

리트코드 - Two Sum

해당 문제를 당시에 딕셔너리를 활용해서 문제를 풀었었다.
시간 복잡도는 입력값인 리스트의 길이만큼 순회하여야 하므로 O(n), 공간 복잡도도 리스트의 길이 만큼 딕셔너리를 생성하게 되므로 O(n)의 시간복잡도가 발생한다.
그런데 멘토님으로부터 이런 피드백을 받았다.

혹시 공간복잡도를 O(1) 로 하는 방법도 있을까요?

 

당시에는 이렇게 답변을 했었다. 

현재 코드는 딕셔너리를 사용하기 때문에 입력 배열인 nums의 길이만큼의 즉 O(n)의 공간복잡도를 가집니다. 그러면 추가 메모리를 발생하지 않도록, 기존 리스트를 이중 순회하는 방식이 있습니다. 하지만 이럴 경우 시간 복잡도가 O(n^2)이 된다는 문제가 있습니다.

 

다음과 같은 추가 질문을 해주셨다.

1 번에 대해서 이중 순회 하는 것 말고, 좀 더 좋은 방법이 있을까요?
예를 들어서 저희 서버가 4GB 의 램을 가지고 있다고 할때, 100GB 크기의 리스트에 대해서 two sum 을 하고자 하면, 어떤 방법이 제일 효율적일까요?

 

이후 해당 질문에 대해 생각해보고 리스트에 대해서 청크로 분리하고, 각 청크들을 이진 탐색을 진행하면 시간 복잡도가 O(logn)이라고 답변을 했지만, 당시에 정리되지 않은 답변이라 해당 답변을 리서치를 해서 보충해 보려고 한다.

100GB 크기의 리스트에 대해 특히 4GB의 RAM 제한이 있는 경우 Two Sum 문제를 이중 순회로 푸는 것은 시간 복잡도가 O(n^2)이므로 매우 큰 리스트에는 적합하지 않다.

외부 정렬과 이진 탐색

1. 외부 정렬(External Sorting):
   • 먼저, 100GB 리스트를 작은 청크로 나누어 외부 정렬을 사용해 각 청크를 정렬한다. 외부 정렬은 디스크 기반의 정렬 방법으로, 큰 데이터를 메모리 제한 내에서 정렬할 수 있게 해준다.
   •  외부 정렬은 정렬할 데이터가 컴퓨팅 장치의 주 메모리(보통 RAM)에 들어가지 않고 대신 속도가 느린 외부 메모리(보통 하드 드라이브)에 있어야 할 때 필요하다.
   • 아이디어는 간단하다. 크기가 매우 크기 때문에 모든 요소를 한 번에 정렬할 수 없다. 따라서 데이터를 청크로 나눈 다음 병합 정렬을 사용하여 정렬한다. 그런 다음 정렬된 데이터를 파일로 덤프한다. 이제 개별 청크를 정렬한 후. 정렬된 배열 k개를 병합하는 아이디어를 사용하여 전체 배열을 정렬한다.
     https://www.geeksforgeeks.org/external-sorting/
2. 이진 탐색(Binary Search):
   • 정렬된 청크에 대해, 각 숫자에 대한 보완(Target - num) 숫자를 이진 탐색으로 찾는다. 이진 탐색의 시간 복잡도는 O(log n)이므로, 각 청크에서 보다 빠르게 원하는 숫자를 찾을 수 있다.

이 관점을 문제에 적용해보자.

1. 배열을 정렬한다. (시간 복잡도: O(n log n))
2. 각 요소에 대해, 정렬된 배열에서 이진 탐색을 사용해 타겟 값에서 현재 요소를 뺀 값이 존재하는지 확인한다. (시간 복잡도: O(n log n))

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_and_idx = [(num, idx) for idx, num in enumerate(nums)]
        num_and_idx.sort()

        for i in range(len(nums)):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if num_and_idx[mid][0] == target - num_and_idx[i][0]:
                    if mid != i: # 두 요소가 서로 다른 인덱스를 가질 때만 반환
                        return sorted([num_and_idx[i][1], num_and_idx[mid][1]])
                    else: # 같은 요소를 참조하는 경우, 이진 탐색 계속
                        if mid + 1 < len(nums) and num_and_idx[mid + 1][0] == target - num_and_idx[i][0]:
                            return sorted([num_and_idx[i][1], num_and_idx[mid + 1][1]])
                        elif mid - 1 >= 0 and num_and_idx[mid - 1][0] == target - num_and_idx[i][0]:
                            return sorted([num_and_idx[i][1], num_and_idx[mid - 1][1]])
                        break
                elif num_and_idx[mid][0] < target - num_and_idx[i][0]:
                    left = mid + 1
                else:
                    right = mid - 1
        return None

 

1. 각 숫자에 대해, 이진 탐색을 사용하여 target - 현재 숫자와 일치하는 다른 숫자를 찾는다.
2. 같은 요소를 참조하지 않는 경우, 두 숫자의 인덱스를 반환한다.
3. 그렇지 않을 경우 이진 탐색이 멈춰진 부분의 양 옆 인덱스를 탐색한다.
4. 이진 탐색은 각 숫자에 대해 O(log n) 시간이 소요되고, 전체 배열에 대해 이진 탐색을 수행하므로 전체 시간 복잡도는 O(n log n).

문제 해결을 위해 우리는 배열 nums의 각 요소와 해당 요소의 원래 인덱스를 튜플 형태로 저장했다. 이를 nums_with_index라는 새로운 배열에 저장하고, 이 배열을 정렬한다.

Python의 sort() 메서드는 평균적으로 O(n log n)의 시간 복잡도를 가진다. Python은 팀소트(Timsort) 알고리즘을 사용하여 정렬을 수행하는데, 이는 병합 정렬과 삽입 정렬의 장점을 결합한 알고리즘이다.

https://www.geeksforgeeks.org/timsort/

팀소트(Timsort) 알고리즘의 기본 개념은 데이터의 기존 순서를 활용하여 비교 및 교체 횟수를 최소화하는 것이다. 배열을 이미 정렬된 실행이라는 작은 하위 배열로 나눈 다음 수정된 merge-sort 알고리즘을 사용하여 이러한 실행을 병합함으로써 정렬을 달성한다고 한다.

TimSort - Data Structures and Algorithms Tutorials - GeeksforGeeks