Python으로 푸는 LeetCode 1. Two Sum

LeetCode 1. Two Sum

이 문제는 주어진 배열에 있는 두개의 원소를 더해 target 값을  항상 만들 수 있을 때

그 두개의 원소의 index 값을 반환하도록 코드를 짜야 한다.

LeetCode에서 문제 보기

LeetCode에서 푼 문제 리스트 보기

github에서 코드 보기

예시로 문제 이해하기

nums = [2, 7, 11, 15]  target = 9

nums[0] + nums[1] = 2 + 7 = 9

# output : [0, 1]

Related Topic

Array, Hash Table

문제 풀이

input의 List는 정렬되어 있지 않으므로 먼저 정렬을 한다.

첫번째 값부터 검사를 시작한다. 첫번째 값이 target 값을 만들기 위해서는 뒤에 반드시 (target - 첫번째 값)이 들어 있어야 한다.

(target - 첫번째 값)이 첫번째 값 이후의 index부터의 배열에 들어있는지 확인하고 있으면 그 즉시 해당 index를 반환한다. 

파이썬 코드는 정렬된 array에서 검색했을 경우와, 정렬되지 않았을 경우에 Rumtime 속도를 비교할 수 있도록 두 코드를 모두 넣었다.

초기에는 정렬된  배열에서 target 값보다 큰 값의 경우에는 탐색할 필요가 없다고 생각하여 배열의 어느 부분까지만 검색을 할지 결정하는 함수를 만들었으나

입력되는 배열에서 음수가 있을 거라고는 생각하지 못했기 때문에, findLastIndex를 제거하고 코드 테스트를 진행하고 문제를 풀었다.

def findLastIndex(start, end, nums, target):
    mid = (start + end) // 2
    mid_v = nums[mid]
 
    if mid_v == target:
        i = mid + 1
        while mid_v == nums[i]:
            i += 1
            mid = i
        return mid
 
    # 동일한 값이 없을 경우
    if start >= end:
        if start < 2:
            return len(nums) - 1
        return start
 
    # 범위 축소
    if mid_v < target:
        start = mid + 1
    else:
        end = mid - 1
    return findLastIndex(start, end, nums, target)
 

파이썬 코드 - 정렬함

정렬 여부가 속도에 큰 차이를 만들고 있음을 알 수 있다.  x in s의 timeComplexity가 O(n)이며 이것은 정렬된 배열에서 원하는 값을 찾으려고 할 때가 정렬되지 않은 경우보다 빠르기 때문이다.

class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
        sorted_nums = sorted(nums) # ascending order
        last_index = len(nums) - 1
        # 0부터 last_index 까지만 검사하면 된다.
        for i in range(0, last_index):
            current_v = sorted_nums[i]
            extra_v = target - current_v
            if extra_v in sorted_nums[i + 1:last_index + 1]:
                first_index = nums.index(current_v)
                second_index = nums.index(extra_v)
                if first_index == second_index:
                    second_index = (first_index + 1) + nums[first_index+1:].index(extra_v)
                return [first_index, second_index]
            

class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
        
        last_index = len(nums) - 1
        # 0부터 last_index 까지만 검사하면 된다.
        for i in range(0, last_index):
            current_v = nums[i]
            extra_v = target - current_v
            if extra_v in nums[i + 1:last_index + 1]:
                first_index = nums.index(current_v)
                second_index = nums.index(extra_v)
                if first_index == second_index:
                    second_index = (first_index + 1) + nums[first_index+1:].index(extra_v)
                return [first_index, second_index]