LeetCode 1번 Two Sum_투 포인터

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

---

문제 파악

주어진 리스트에서 합해서 target과 같은 넘버가 되는 지 확인하는 문제

접근 방법

1주차와는 다르게 투 포인터를 사용해서 풀어보자!

이유는 1주차에서는 이중반복문을 사용해서 풀었는데 이는 $O(n^2)$이므로 $n$이 크다면 시간초과가 날 가능성이 있다. 효율적인 성능을 위해 투 포인터를 사용해보자.

우선 배열을 정렬해놓고 그 중 가장 큰 값과 가장 작은 값을 먼저 선택한다. 두개를 더한 값이 target보다 작다면 가장 작은 값을 한 칸 오른쪽으로 옮긴다. 반대로 target보다 크다면 가장 큰 값을 한 칸 왼쪽으로 옮긴다. 이럴수록 두 값의 합이 target에 더 가까워진다. 이것을 반복하다보면 두 수의 합이 target과 같아지는 경우를 구할 수 있다.

이 경우 배열 정렬에 $O(nlogn)$, 합이 target이 되는 두 수를 구하는데 $O(n)$이 걸리므로 전체 시간복잡도는 $O(nlogn)$이 되어 앞선 방법보다 훨씬 빠르게 답을 구할 수 있다.

코드 구현

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 원본 리스트의 값과 인덱스를 튜플로 저장
        indexed_nums = [(num, idx) for idx, num in enumerate(nums)]
        
        # 값만 정렬하여 사용하기 위한 리스트
        sorted_nums = sorted(indexed_nums, key=lambda x: x[0])
        
        l, r = 0, len(sorted_nums) - 1
        
        # 왼쪽 포인터가 오른쪽 포인터보다 작을 동안 반복한다.
        while l < r:
            current_sum = sorted_nums[l][0] + sorted_nums[r][0]
            
            if current_sum < target:
                l += 1
            elif current_sum > target:
                r -= 1
            else:
            
                # 원본 리스트에서의 인덱스를 반환
                return [sorted_nums[l][1], sorted_nums[r][1]]

        # 솔루션이 보장되지 않는다면 빈 리스트를 반환
        return []

배우게 된 점

1. enumerate

enumerate는 파이썬 내장 함수로, 리스트, 튜플 등 반복 가능한 객체(iterable)를 인덱스(index)와 함께 반복할 수 있게 해준다. enumerate를 사용하면 기본적으로 두 개의 값을 반환합니다

• 현재 요소의 인덱스
• 그 요소 자체

# Enumerate를 사용했을 때
indexed_nums = [(num, idx) for idx, num in enumerate(nums)]

# Enumerate를 사용하지 않았을 때
indexed_nums = []
for idx in range(len(nums)):
    num = nums[idx]
    indexed_nums.append((num, idx))

• nums 리스트를 enumerate를 통해 인덱스와 함께 반복한다.
• enumerate(nums)는 각 요소에 대해 (인덱스, 요소) 쌍을 생성한다.
• 리스트 내포(list comprehension)를 사용하여 (num, idx) 형태의 튜플을 생성한다.