LeetCode[ 219 | Python ] Contains Duplicate II

문제

https://leetcode.com/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150

정수 배열 nums와 정수 k가 주어지면 nums 다음의 조건을 충족하는 임의의 주소값 i, j가 존재할 수 있을지에 대한 true, false를 반환해야 하는 문제.

• i, j가 서로 같은 값을 가리킨다.
• i와 j 사이의 거리가 k이하이다.

풀이

시도

실행 시간 : 991ms
메모리 : 31.2MB

1. 해시테이블에 nums의 데이터들을 추가한다.
2. 저장된 해시테이블에 길이가 2 이상인 리스트가 존재한다면, 원소를 비교하기 위해 두번째 원소부터 순회한다.
   1. 두 원소의 거리가 k이하라면 True 를 반환한다.
3. 성공적으로 모든 코드를 수행했다면 False를 반환한다.

이 코드는 two sum 문제와 같이 데이터를 저장함과 동시에 판단할 수 있을 것이라는 생각이 들었다.

동시에 판단하기만 하면 해시테이블의 키를 추출해 다시 순회하여 시간복잡도를 필요 이상으로 증가시키지 않을 것이라고 판단 되었다.

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):

        dic = {}

        for i in range(len(nums)):
            if nums[i] in dic:
                dic[nums[i]].append(i)
            else:
                dic[nums[i]] = [i]
    
        for i in dic.keys():
            if len(dic[i]) >= 2:
                for j in range(1, len(dic[i])):
                    if abs(dic[i][j-1] - dic[i][j]) <= k:
                        return True
        return False 

개선

실행시간 : 471ms
메모리 : 24.8MB

위에서 언급한 것과 같이 해시테이블에 이미 i가 가리키는 값이 존재할 경우 이미 존재하는 주소와의 거리가 k 이하라면 True를 반환하도록 하고, 존재하지 않는 경우 계속해서 저장되어 있는 주소값을 갱신하도록 수정했다.

O(2n) 이던 시간 복잡도가 O(n) 으로 줄어 들었으니 당연히 실행시간은 두배에 가깝게 감소했다.

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        dic = {}

        for i in range(len(nums)):
            if nums[i] in dic:
                if abs(dic[nums[i]]  - i) <= k : 
                    return True
            dic[nums[i]] = i
        return False
    

생각 & 정리

주어진 것을 잘 활용하는 것은 언제나 중요하다.
더군다나 유한한 컴퓨터 자원을 이용해야하는 경우는 더욱이 그렇다고 생각한다.
주어진 것을 잘 이용하지 못하는 것으로 수행시간도, 메모리도 프로세스도 더욱 복잡해질 것을 생각하니 좋은 습관을 잘 길러야겠다는 생각이 들었다.