Python - Leetcode(easy): Two Sum

리트코드 [난이도 EASY] - Two Sum (Python)

• 코테 링크: https://leetcode.com/problems/two-sum/

1. 첫 시도 : iteration 사용

nums 리스트 안의 요소를 하나씩 돌면서 target 숫자를 만들어 낼 수 있는 다른 요소가 존재하는지 확인하는 방법으로 문제를 풀었다.
문제를 풀면서 한 번 시간을 걸린 부분이 new_list라는 새로운 list를 만들어낼 때, 리스트를 그대로 대입하였더니 참조 주소를 복사하게 되어서 new_list.pop()을 해주었을 때 기존의 nums 리스트도 수정이 되는 문제가 발행하였다.

리스트를 복사할 때는 꼭 a = deepcopy(list)를 쓰도록 습관화 해야겠다.

🔽 첫 시도 코드

class Solution(object):
    from copy import deepcopy
    
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        output = []
        for i in range(len(nums)):
            y = target - nums[i]
            new_list = deepcopy(nums)
            new_list.pop(i)
            if y in new_list:
                output += [i]
                output += [new_list.index(y)+1]
                return output
            else:
                pass

위의 코드로 주어진 예제1,2,3을 모두 통과하여 제출하였다. 하지만 결과는 ‘Time Limit Exceeded’🕐🕐🕐

2. 두번째 시도: hash map 사용

hint3을 보면 이렇게 나와있다.

The second train of thought is, without changing the array, can we use additional space somehow?
Like maybe a hash map to speed up the search?

빠른 서치를 위해서 자료구조 해시 맵을 사용해보라는 조언이다.
배열을 바꾸지 않고 추가적인 공간을 어떻게든 써본다는 것은 무슨 말일까?
Hash map, Hash table에 대해 구글링하면서 고민해보았다.

2.1. 자료구조 - 해시 테이블 (Hash Table) 알아보기

해쉬테이블

• 해쉬 구조란?
  • Key와 Value가 한 쌍으로 이루어진 데이터 구조이다
  • 파이썬에서 dictionary 타입이 해쉬 테이블과 같은 구조이다
  • 공간을 많이 사용하지만 key를 이용해서 데이터를 찾기 때문에 속도를 빠르게 만드는 구조이다
  • 주요 상황: 검색이 많이 필요한 경우, 저장/삭제/읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용
• 장점:
  • 데이터 저장/검색 속도 빠름
  • Key에 대한 데이터가 있는지 중복 확인이 쉽다.
• 단점:
  • 저장공간이 많이 필요하다
  • 여러 키에 해당하는 주소가 동일하면 충돌을 해결하기 위한 별도 자료구조가 필요하다(충돌 해결 알고리즘)
• 시간 사용:
  • 충돌이 없는 일반적인 경우: O(1)
  • 모든 충돌이 발생하는 경우(최악의 경우): O(n)
• 용어
  • Hash 해쉬: 임의 값을 고정 길이로 변환하는 것
  • Hash function 해쉬 함수: 특정 연산을 이용해서 key를 받아서 값(value)를 가진 공간의 구조로 바꾸어주는 함수
  • Hash table 해쉬 테이블: 해쉬 구조를 사용하는 데이터 구조
  • Hash value/adress 해쉬 값/주소: key값을 해쉬 함수에 넣어서 얻은 주소값. 이 값으로 슬롯을 찾아감.
  • Slot 슬롯: 한 개의 데이터를 저장할 수 있는 공간을 의미 (아래에서는 bucket)

출처: 위키피디아

해쉬 함수와 키 생성 함수

to be continued…