[LeetCode]1. Two Sum

신동재·2021년 9월 13일
0

코딩테스트 준비

목록 보기
2/8
post-thumbnail

리트코드 코딩 테스트 준비
https://leetcode.com/problems/two-sum/5
문제에 대한 자세한 설명은 다음 사이트에서 확인 할 수 있다.

❓ 문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

❗ 접근 방법

문제는 리스트의 두 수를 더할 때 target이 되는 두 수의 index값을 return 하는 문제 이다.

첫번째로 가장 먼저 떠오른 방법은 Brute-Force 방법을 이용하여 리스트의 마지막 요소들까지 모두 차례대로 비교하며 정답을 찾을때 까지 진행하는 방법이다.
이중 for문을 이용하여 경우의 수를 모두 탐색하여 조건에 만족할 경우 return 한다. O(N2)

두번째로 떠오른 방법은 모든 조합을 비교하지 말고 target - num1를 통해 num2을 찾는 방법이다. O(N)

⭕ 내가 작성한 코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        answer = []
        for i in range(len(nums)) :
            for j in range(i+1,len(nums)) :
                if nums[i] + nums[j] == target :
                    return [i,j]

💯 다른사람이 풀이한 코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i,v in enumerate(nums) :
            complement = target - v
            if complement in nums[i+1:] :
                return nums.index(v), nums[i+1:].index(complement) + (i+1)

동일한 값이 리스트에 있는 테스트 케이스 경우에는 오류가 날 수 있기 때문에
num[i+1:].index(complement) + (i+1) 은 무조건 앞에부분의 인덱스는 0이되므로 i+1을 더해준다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
    
        #키와 값을 바꿔서 딕셔너리로 저장
        for i, num in enumerate(nums):
            nums_map[num] = i

        #타겟에서 첫 번째 수를 뺀 결과를 키로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return nums.index(num), nums_map[target - num]

딕셔너리는 index함수가 없기 때문에 다음과 같이 nums_map은 key nums_map[]는 value에 접근할 수 있다. 인덱스와 값을 이용하는 문제에서는 enumerate를 사용하면 편하다.

비교나 탐색 대신 한번에 정답을 찾을 수 있는 딕셔너리를 이용한 방법으로 조회는 O(1) , 전체는 O(N)
딕셔너리는 해시테이블로 구현되어 있기 때문에 가장 빠르다는 장점이 있다.

🧑🏻 후기

문제의 핵심은 정렬되지 않은 리스트에서 탐색을 하는 것이다.

투포인터 알고리즘을 사용하려 했으나 투포인터는 sort가 이미 된 배열에서만 사용할 수 있다.

따라서 다른사람 풀이처럼 딕셔너리를 이용하니 첫번째 브루트-포스 방법보다 약 100배 성능이 좋아졌다.

알고리즘의 세계는 놀라운 것 같다.

profile
Software Developer / 1997.12.05

0개의 댓글