1. Two Sum 공간복잡도 O(1)로 풀어보자..

https://leetcode.com/problems/two-sum/description/

Two Sum - LeetCode

주어진 문제를 풀면서 추가적인 리스트를 생성하지 않고, 입력된 nums 배열을 직접 사용하는 방법을 사용하여야 한다.

 

해시 테이블을 사용하면 추가적인 공간이 필요하므로, 공간 복잡도가 O(1)이 아니게 된다.

그러나, 문제의 제약사항을 고려하여 해시 테이블을 사용하지 않고 풀이하는 방법을 생각해볼 수 있다.

Two Pointers 방법을 사용하되, 먼저 배열을 정렬하는 방식이다.  정렬된 배열에서 두 포인터를 사용하여 합이 타겟 값과 일치하는 두 수를 찾는 것이다.

하나의 포인터는 배열의 시작 부분에, 다른 하나는 끝 부분에 위치시키고, 두 수의 합이 타겟 값보다 작으면 시작 포인터를 증가시키고, 두 수의 합이 타겟 값보다 크면 끝 포인터를 감소시킨다.

시간 복잡도는 O(n log n)+ O(n) = O(n log n)이다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        original_nums = list(nums)  # 원본 배열 복사
        nums.sort()  # 배열 정렬 O(nlog n)
        left, right = 0, len(nums) - 1 
        
        while left < right: # O(n)
            current_sum = nums[left] + nums[right] # O(1)
            if current_sum == target:
                break
            elif current_sum < target:
                left += 1
            else:
                right -= 1

        # 원본 배열에서 인덱스 찾기
        first = original_nums.index(nums[left]) # O(1)
        original_nums[first] = None  # 첫 번째 요소 제거 # O(1)
        second = original_nums.index(nums[right]) # O(1)

        return [first, second]

 

nums의 원래 인덱스를 저장하여야 하기 때문에 원본배열을 복사해놓긴 해야하는 풀이다. 이것도 공간복잡도에 포함시킬 경우 O(1)의 공간복잡도를 가진다.

 

원본 배열의 순서를 변경하지 않고 두 수의 합이 특정 타겟 값을 만족하는 인덱스를 찾는 것은 해시 테이블을 사용하지 않고는 구현하기 어려운 문제이다...

 

풀이 2

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for idx, num in enumerate(nums):
            res = target - num
            if res in nums and nums.index(res) != idx:
                return [idx, nums.index(res)]

이 코드는 리스트 nums를 한 번 순회하면서 각 요소에 대해 리스트 전체를 순회하여 해당 값을 찾는다. nums.index(res)도 최악의 경우 전체 리스트를 순회한다.

따라서, 이 코드의 시간 복잡도는 이중 for 루프와 유사하게 O(n^2)이다.