[알고리즘]Two Sum(LeetCode 문제) python 풀이(정렬, 해시)

LeetCode 문제

leetcode.com/problems/two-sum/

 

 

문제는 Input nums 정수형 리스트와 이 리스트로 만들어야할 값 target이 있고 리스트에서 target을 만들 수 있는 인덱스 2개를 구하면 된다.

 

첫번째로 풀 수 있는 방법은 첫번째 인덱스와 뒤에있는 나머지 인덱스와 더해보고 두번째 인덱스와 그 뒤에 있는 인덱스와 더해보는 방법이 있다. 대부분 처음에 이 방법을 떠올릴 것이다.

 

 

[풀이] 1. Brute Force

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            #i 다음 인덱스부터 loop
            for j in range(i+1, len(nums)):
                # 첫번째 인덱스부터 뒤에있는 인덱스를 더하고 target이 맞는지 확인
                if target == (nums[i] + nums[j]):
                    # target이 맞다면 2개 인덱스 리턴
                    return [i, j]

 

이 방법으로 풀어도 통과는 할수 있지만 Runtime이 길어서 nums 길이가 길어질수록 엄청난 시간이 소요된다. 

 

 

그래서 시간을 줄이기 위해 정렬 방법으로 풀어보았다.

먼저 nums를 정렬한 다음에 nums의 처음 인덱스의 숫자와 nums의 마지막 인덱스의 숫자를 더해보고 target보다 크면 nums의 마지막 인덱스 -1 하고 작으면 처음 인덱스를 +1 해서 target을 찾도록 코딩하였다.

 

[풀이] 2. Solting

def twoSum(self, nums, target):
    origin = {}
 
    # 정렬하기전 nums의 데이터를 origin에 담음
    for idx, val in enumerate(nums):
        if val in origin:
            origin[val].append(idx)
        else:
            origin[val] = [idx]
 
    nums.sort()
 
    left, right = 0, len(nums)-1
 
    # nums[left] + nums[right]가 target보다 작으면 left+1, 크면 right-1
    # left가 right보다 커지면 루프 종료
    while left < right:
        if (nums[left] + nums[right]) < target:
            left += 1
        elif (nums[left] + nums[right]) > target:
            right -= 1
        else:
            # origin[nums[left]]는 자료형이 리스트여서 [0], [-1]을 붙임
            return [origin[nums[left]][0], origin[nums[right]][-1]]
        

def twoSum(self, nums, target):
    # target - nums 값을 seen에서 찾고 없으면 seen에 추가        
    seen = {}
 
    for idx, val in enumerate(nums):
        another = target - val
 
        if another in seen:
            # seen에 넣었던 값이 먼저 return 돼야 한다.
            return [seen[another], idx]
        else:
            seen[val] = idx
 
    return [-1, 1]