Hash_table

  Leetcode에서 문제를 풀면서 알고리즘 공부를 하고 있다.

 

  들어갈 때마다 daily challenge 중에 난이도가 easy인 문제들은 한번씩 확인하고 풀 수 있다면 풀어보는 편인데

오늘의 문제는

https://leetcode.com/problems/contains-duplicate-ii/

Contains Duplicate II - LeetCode

  예전에 풀어봤던 문제에서 조건을 추가한 것으로 index간의 간격을 k 라는 조건으로 두었다. 

  첫번째 접근법으로는 index를 len(nums)-k 까지 도는 for loop를 만들고 loop마다 초기화 되는 pointer를 새로 생성해서 

nums[i] == nums[i+pointer] 조건이 맞지 않을 경우, k까지 1씩 증가하도록 만들었다. 

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        i,j = 0, len(nums)-k
        while i < j:
            pointer = 1
            while pointer <= k:
                if nums[i] == nums[i+pointer]:
                    return True
                else:
                    pointer += 1
            i += 1
        
        return False
        
 # 잘못했음

  window(pointer)는 1부터 k까지 존재할 수 있고, i 부터 window를 늘려나가 k까지 확인하면서 num[i] == nums[i+pointer]가 존재하면 결과는 true로 return 끝나고 존재하지 않는다면 i +1 부터 pointer는 초기화하여 다시 탐색하는 방식이다. 

  근데 문제가 nums = [99, 99], k = 2 에서 발생했다. k와 len(nums)가 같다면 첫번째 while문에서 조건이 끝나 return False로 나왔다. len(nums)와 k의 조건을 모두 만족하도록 예외를 조건을 생각하지 않고 생각나는대로 만들어서 생긴 결과물이다. 

 

  지난번에 풀었던 문제는 k라는 조건이 존재하지 않아 쉽게 접근했었는데.

Solution을 보고 문제의 해답과정을 이해할 수 있었다. 

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hset = {}
        for idx in range(len(nums)):
            if nums[idx] in hset and abs(idx - hset[nums[idx]]) <= k:
                return True
            hset[nums[idx]] = idx
        return False

  hash_table은 key:value 값으로 정해져있어 key를 통해 고유한 index 값을 가지고 있다고 볼 수 있다.

 

  이 문제의 접근법은 기존에 존재하는 num과 이후에 list안에 같은 num값이 존재해야하고 그 둘간의 index차이가 k보다 작아야하는 조건을 생각하는 것이다. value to index 형태의 해시테이블을 만들고 nums[idx] 가 해시 테이블에 없다면 테이블에 값을 입력하고 값이 존재한다면  해시테이블에서 가져온 index값과 idx값을 비교하는 방법으로 문제를 해결할 수 있다. 

 

  여러가지 접근 방법이 있겠지만 Solution을 보고 hash_table을 사용하여 key :value 값을 비교하는 방식에 대해서 배울 수 있었다. for index, value in enumerate(nums): 를 사용해도 똑같이 index와 value값을 저장하는 것이니까 그것도 써 볼수 있겠다.