03/18 알고리즘 문제풀이 - 1. Two Sum (Leetcode)

문제

• Leetcode 알고리즘 문제
• 1. Two Sum (Easy)
• 문제 내용 : [링크]
  

내가 작성한 코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        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:
            if nums[l][0] + nums[r][0] > target:
                r-=1
            elif nums[l][0] + nums[r][0] < target:
                l+=1
            else:
                return [nums[l][1], nums[r][1]]
  

• nums 에서 중복되지 않는 두 수를 뽑았을 때 target 값이 나오는 수의 인덱스 2개를 추출하는 문제이다.

• 시간복잡도 계산 결과, O(n^2) 으로 풀이할 경우, 시간초과 발생. two pointer로 문제 접근

• two pointer로 문제 접근 시, nums를 정렬해줘야 한다. 하지만 구해야하는건 원래 nums의 인덱스이므로, 정렬 전 인덱스를 포함한 리스트를 작성해준다. nums = [[n, i] for i, n in enumerate(nums)]

• nums.sort(key = lambda x: x[0]) 로 nums를 정렬해준다.

• 투 포인터 설정 (l = 0, r = len(nums)-1)

• 투 포인터의 인덱스의 nums 값 합이 target 보다 큰 경우, r을 왼쪽으로 한 칸 이동한다. 반대로 합이 target 보다 작은 경우, l 값을 오른쪽으로 한 칸 이동

• 두 합이 target과 같아진 경우, 정렬 전 nums의 인덱스를 return 한다.

⭐⭐⭐⭐⭐

1. 시간복잡도를 고려한 문제 접근 (완전탐색은 O(n^2) 이므로 사용불가, 정렬은 O(nlogn) 이므로 사용가능

2. 투 포인터 문제 접근은 리스트를 정렬한 후 가능

3. nums = [[n, i] for i, n in enumerate(nums)] 처럼 기존 리스트 정보를 저장할 수 있다.