Two Sum

Two Sum - LeetCode

접근 방법 [필수 작성]

제한 조건 확인

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

→ 무조건 1개 해는 존재하며, 같은 값을 2번 사용할 수 없음.

→ 각 원소는 한번씩만 참조하면 되며 투포인터가 크로스되거나, 리스트길이가 0이나 1인 경우는 고려 안해도됨

완전탐색을 해도 nums 길이가 10^4 이어서

O(n^2) 으로 풀 수 있지만, 연산수가 10^8 이기 때문에 간당간당하다.

nlogn 으로 풀 수는 없을까? → 정렬과 투포인터를 이용해서 O(nlogn) 으로 풀 수 있다!

아이디어

정렬 후 양 끝 포인터를 기준으로 target 을 기준으로 대소를 비교하여 왼쪽 포인터를 옮길지 오른쪽 포인터를 옮길지 결정하여 O(n) 안에 탐색을 완료한다!

만약, 왼쪽 오른쪽이 같아지는 지점이 발생하면 해당 리스트안에는 target 을 만족하는 two_sum 이 존재하지 않는다!

시간복잡도

O(nlogn)

2^10 ~~ 10^3 / 2^3 ~~ 10

따라서 10^4log(2^32^10) = 13*10^4 = 130000

자료구조

코드 구현 [필수 작성]

#2시40분 시작 -> 3시5분 끝
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_nums = sorted(nums)
        left_pointer = 0
        right_pointer = len(sorted_nums)-1
        
        curr_two_sum = sorted_nums[left_pointer] + sorted_nums[right_pointer]

        while left_pointer <= right_pointer:
            print(left_pointer,right_pointer)
            if curr_two_sum == target:
                break
            elif curr_two_sum > target: 
            #오른쪽포인터를 더 작은 원소를 탐색하게 하여 현재 합을 낮춤
                curr_two_sum -= sorted_nums[right_pointer]
                right_pointer -= 1
                curr_two_sum += sorted_nums[right_pointer]
            elif curr_two_sum < target:
            #왼쪽포인터를 더 큰 원소를 탐색하게 하여 현재 합을 높힘
                curr_two_sum -= sorted_nums[left_pointer]
                left_pointer += 1
                curr_two_sum += sorted_nums[left_pointer]
        
        left_elem = sorted_nums[left_pointer]
        right_elem = sorted_nums[right_pointer]

        return [nums.index(left_elem),len(nums)-1-nums[::-1].index(right_elem)]

배우게 된 점 [ 필수 X ]

해설코드

def twoSum(nums, target):
    nums = [[n, i] for i, n in enumerate(nums)]
    nums.sort(key=lambda x: x[0])
    l, r = 0, len(nums) - 1

    while l < r:
        num_sum = nums[l][0] + nums[r][0]
        if num_sum == target:
            return [nums[l][1], nums[r][1]]
        elif num_sum > target:
            r -= 1
        else:
            l += 1

원래 원소의 위치를 파악하기 어려워서 문제의 특성을 이용해서 편법으로 위치를 찾다보니 아래 코드처럼 코드가 굉장히 지저분해지고 가독성도 떨어지게 되었다.

[nums.index(left_elem),len(nums)-1-nums[::-1].index(right_elem)]

해설코드는 이 문제를 enumerate 함수를 활용하여 원래 원소의 위치 인덱스를 튜플형태로 효과적으로 저장해주고 있다. 특정 원소의 인덱스를 필요로 할때는 enumerate를 적극적으로 활용해보려고 노력하자.

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

수고하셨습니다!