[리트코드/leetcode/python] 1. Two Sum

이미지를 누르면 문제 링크를 보실 수 있습니다.

 

리트코드에서의 1번문제입니다.

문제를 설명해보자면, 입력값으로 nums 라는 숫자배열이 주어집니다. 그리고 target값도 입력값으로 주어지는데요, nums배열에서 두 숫자를 더해 target을 만들 수 있다면, 해당 두 숫자의 인덱스 값을 배열 형태로 출력하는 문제입니다. 

문제 자체는 비교적 간단한 문제입니다만, 이 문제를 어떻게 효율적으로 풀어야 할지는 고민해봐야 할 부분입니다.

 

해당 문제를 직관적으로 풀자면 for문을 두 번 돌면 됩니다.

대략적인 코드는 아래와 같겠죠.

for i in range(len(nums)):
	for j in range(i+1,len(nums)):
    	if (nums[i] + nums[j]) == target:
        	return [i,j]

 

하지만, 위와 같이 푼다면, 이미 시간복잡도는 O(n^2)이기 때문에, 제약조건에서 nums의 길이가 10^4인 것을 본다면, 시간초과에 걸릴 위험이 있습니다. 보통 시간복잡도는 10^8 정도 보다는 작아야 하니까요.

 

이 문제를 단순 반복문이 아닌 two pointer로 푸는 방법이 있습니다.

그러기 위해선 정렬알고리즘을 써야 하는데요, 정렬이 안 된 리스트를 정렬을 할 때 걸리는 시간복잡도는 보통 O(NlogN)입니다. 파이썬 내장 함수 기준으로 말이죠.

 

그러면, 정렬 알고리즘을 tow pointer기법과 적절히 사용한다면 우리는 시간복잡도를 O(N^2) 에서 O(NlogN)으로 줄일 수 있다는 소리겠죠!

 

그렇다면 개선된 코드를 먼저 살펴봅시다.

class Solution(object):
    def twoSum(self, nums, target):

        
        sorted_nums = sorted(nums)
        answer = []
        left = 0 
        right = len(nums)-1



        while left < right:

            if sorted_nums[left] + sorted_nums[right] > target:
                right -= 1
            elif sorted_nums[left] + sorted_nums[right] < target:
                left += 1
            else:
                answer.append(nums.index(sorted_nums[left]))
                if sorted_nums[left] == sorted_nums[right] :
                    answer.append(nums.index(sorted_nums[right],(nums.index(sorted_nums[left]))+1,len(nums)))
                else:
                    answer.append(nums.index(sorted_nums[right]))

                break
        
        return answer

코드는 길어졌지만, 시간복잡도는 훨씬 줄은 것을 알 수 있어요.

먼저, two pointer를 쓰려면 정렬을 해야하므로, nums리스트를 sorted()함수를 통해 정렬해줍니다. --> O(NlogN)

left는 정렬된 리스트 sorted_nums의 처음 인덱스인 0부터,

right는 정렬된 리스트 sorted_nums의 끝 인덱스인 len(nums)-1 부터 시작합니다.

 

sorted_nums는 오름차순으로 정렬된 리스트인데요, 우리는 two pointer기법으로 target을 찾아내는데 O(N)의 복잡도만으로 해결할 수 있습니다. for문을 두 번 돌 필요가 없다는 소리죠.

 

sorted_nums[left] + sorted_nums[right] 가 target 보다 크다면, 우리는 right의 자리를 왼쪽으로 하나 옮겨줘야 합니다. 왜냐하면, 해당 리스트는 현재 오름차순으로 정렬되어 있고, left와 right가 가리키는 값들의 합이 target보다 크니까 값을 줄여주기 위해서는 left 위치를 오른쪽으로 이동하는 것보다(증가시키는 것보다) right 위치를 왼쪽으로 이동하는 것(감소해주는 것)이 맞습니다.

 

반대로, sorted_nums[left] + sorted_nums[right] 가 target 보다 작다면, 우리는 target을 향해 가야하니까, 값을 증가시키기 위해 left 위치를 오른쪽으로 증가시캬줘야 겠죠!

 

해당 로직을 left가 right보다 커질 때까지 반복합니다. 보통은 그 전에 while문을 탈출할텐데, left와 right가 같아지기 전까지 값을 못 찾는 다면 해당 리스트에서는 target을 찾을 수 없다는 소리입니다.

 

그렇다면, target을 찾았다면, 해줘야 하는 작업은 무엇인가요? 단순히 retrun [left,right] 를 하는 것은 안됩니다. 우리는 input 값으로 주어진 배열 nums를 정렬시키면서 인덱스를 바라보고 있기 때문에, 원래 리스트인 nums에는 해당 값을 가리키는 인덱스가 다를 수 있기 때문입니다.

예를 들어서, [2,3,1,5,7] 이라는 nums 리스트가 있고, 이를 오름차순 정렬한 리스트 sorted_nums인 [1,2,3,5,7] 가 있을 때, 3을 가리키는 인덱스는 nums에서는 1 이지만, sorted_nums 에서는 2 로 다릅니다.

 

때문에, 최종 답을 구하는 answer리스트에는 본래 nums 리스트에서 sorted_nums[left] 의 값을 가지는 위치인 인덱스 값을 먼저 추가해줍니다.

다음에는, 본래의 nums리스트에서 sorted_nums[right] 값을 가지는 위치의 인덱스를 넣어줘야 하는데, 이 때 주의해야 할 점이

answer.append(nums.index(sorted_nums[right],(nums.index(sorted_nums[left]))+1,len(nums)))

해당 작업을 해줘야 합니다. 해당 작업의 의미는 sorted_nums[right]의 값을 nums에서 찾는데, .index() 함수는 찾고자 하는 값이 처음으로 나오는 인덱스 자리를 반환하므로, sorted_nums[left]와 sorted_nums[right] 값이 같다면, sorted_nums[left] 의 자리 바로 다음부터 끝까지 찾도록 하는 작업입니다.

 

예를 들어서, nums = [3,3] 이고, target 값이 6이라고 가정한다면, 해당 작업을 안해줄 경우 반환하는 answer 리스트는 [0,0] 이 될 것입니다. 우리가 원하는 값은 이 예시에서는 [0,1] 인데, 위 작업을 해줌으로써 원하는 결과를 얻을 수 있겠죠!

 

시간복잡도는 O(N)과 O(NlogN) 둘다 쓰였지만, 최종적인 시간복잡도는 더 큰 복잡도인 O(NlogN)이 되겠습니다. 같은 문제라도, 시간복잡도를 줄이는 방안으로 생각하며 문제를 풀어야겠습니다.

이상 Two Sum 문제에 대해 정리해봤습니다.