Two Sum - LeetCode

[목차]

1. 문제 
2. 문제 설명
3. 문제 풀이 
4. code
5. 배운점

1. 문제
Two Sum - LeetCode

leetcode twosum 문제

2. 문제설명

예제 2를 보자 
[3, 2, 4] , target = 6
output = [1, 2]

저 집합에서 더해가지고 6이 나오는 원소를 구하는 문제이다. 
저기 보면 output(정답)은 1, 2이다. 즉 1번째인 2와 2번째인 4를 더해서 6이 나온다.
(여기서 1번째=2 인것을 이해 못하신 분은 컴퓨터에서는 첫번째가 0으로 시작한다.즉 0번째 3, 1번째 2, 2번째 4 이다. )  

3. 문제풀이

3.1 첫번째 풀이 (Brute Force 방식) 

example2
[3, 2, 4] , target = 6
output = [1, 2]

brute force 방식

위에 그림처럼 하나의 원소가 기준이 되고 오른쪽에서 하나씩 더해서 target이 나올때까지 반복한다. 만약 target이 없으면 아무 값도 output하지 않는다. 

3.2 두번째 풀이

두번째 방식은 두개의 pointer를 이용하는 방식인데 각각 왼쪽과 오르쪽 맨 끝에 left, right로 지정한다. 리스트를 오름차순으로 정렬한다. 그리고서 아래와 같은 알고리즘으로 작동한다. 

[알고리즘]
1) left + right > target
-> 이 경우는 target보다 크기 때문에 right를 -1로 해서 left+right의 값을 줄인다. 
2) left + right < target
-> 이 경우는 left + right의 값이 target보다 작기 때문에 left를 +1 증가해서 target의 값에 근접하도록 조정한다. 
3) left + right = target
-> 이 경우는 우리가 찾던 숫자이기 때문에 바로 left index와 right index를 반환해준다.

맨 마지막에 index값을 찾았다면 그것또한 정렬해서 답이랑 맞춘다. (but leetcode에서 돌릴땐 정렬을 안해도 답이라고 나옴) 

4. code

4.1 첫번째 방식(brute force) 

from typing import List

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

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

-> 첫번째 방식은 위에 설명에 있듯이 하나의 원소를 기준으로 해서 오른쪽 원소를 하나씩 더해서 target이 있는지 확인해본다. 이것은 길이가 짧은 list이면 상관없지만 길이가 길어질수록 시간 복잡도 또한 신경 쓸게 많아진다. 
시간복잡도는 for문이 2번 수행되기 때문에 O(N * N)이 되어서 O(N^2)이 된다.

4.2 두번째 방식

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        left, right = 0, length - 1
        nums = [[value, index] for index, value in enumerate(nums)]
        nums.sort(key=lambda x : x[0])
    
        while left < right:
            sum = nums[left][0] + nums[right][0]
            if sum > target:
                right -= 1
            if sum < target:
                left += 1
            if sum == target:
       	 	result = [nums[left][1], nums[right][1]]
              	result.sort()
               	return result

두번째 방식이 더 빠르고 생각보다 구현도 어렵지 않았다. 그리고 시간 복잡도는 정렬하는 곳에서는 O(NlogN)번 걸리고, pointer 조절하는 곳에서는 O(N)이 걸렸다. 둘이 합친다면 O(N*logN) + O(N) = O(N*logN)이라고 할수 있다.

5. 배운 점

원래는 for문 두번 돌리는 방식으로만 생각을 해보았는데 pointer를 이용해서 구할 수 있다는게 신기하였고, 내 생각의 사고를 깨버린 문제였다. 어떻게 보면 아주 쉬운 단계의 문제였지만 생각보다 고민을 많이 했던거 같다.