[Leetcode Top Interview 150] 219. Contains Duplicate II

난이도 : easy

문제링크

• 정수형 배열 nums와 정수 k가 주어진다
• 서로다른 인덱스 i, j의 요소값에 대하여 아래 두개의 조건을 모두 만족하는지 여부에 대해 boolean 값을 리턴하라
  • nums[i] == nums[j]
  • abs(i-j) <= k

 

1. 접근법

• 해시테이블을 이용한다
• 충돌시, Separate Chaining 기법을 이용하여 같은 key값을 put할 때, overwrite X
• 링크드리스트로 bucket을 생성하여 key, value 형태의 entry들을 요소로 가지도록

 

3. 구현 코드

class Solution {
    // key : nums[index]
    // value : index
    class Entry {
        int key;
        int value;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LinkedList<Entry>[] table;
    public Set<LinkedList<Entry>> chainingTables;
    
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length == 1) {
            return false;
        }

        this.table = new LinkedList[1000000*2+1];
        this.chainingTables = new HashSet<>();

        for (int i = 0; i < table.length; i++) {
            this.table[i] = new LinkedList<>();
        }

        for (int i = 0; i < nums.length; i++) {
            put(nums[i], i);            
        }

        for (LinkedList<Entry> bucket : this.chainingTables) {
            int left = 0, right = 1;            
            while (right < bucket.size()) {
                System.out.println(bucket.get(right).value + " : " + bucket.get(left).value);
                if (bucket.get(right).value - bucket.get(left).value <= k) {
                    return true;
                }

                left++;
                right++;
            }            
        }

        return false;
    }

    private void put(int key, int value) {
        int idxOfKey = hash(key);
        LinkedList<Entry> bucket = this.table[idxOfKey];
        Entry newEntry = new Entry(key, value);
        
        if (bucket.isEmpty()) {
            bucket.add(0, newEntry);
        } else {
            bucket.add(bucket.size(), newEntry);
            this.chainingTables.add(bucket);
        }
    }

    private int hash(int key) {
        if (key < 0) {
            key = key*-1 + this.table.length/2 - 1;
        }

        return key;
    }
}

• 해시테이블을 구현하였음
  • key : 요소의 값
  • value : 요소의 인덱스
• bucket들을 링크드리스트의 배열로 저장하여서, key가 음수가 될수 있어 요구사항에 적절하지 않았다
• 필요하지 않은 공간을 생성해야 해서 배열로 구현했으면 안됬다
• 결국 공간복잡도, 시간복잡도 초과로 실패하였다

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함

5. 개선점

• array 기반이 아닌 list로 entry를 hashtable에 저장해야 함
  • 동적으로 크기가 증가하도록

 

6. 회고

• 풀다가 생각이 안나 GPT에게 물어보았다

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }

        return false;
    }
}

(출처 : chatgpt)

• 자바의 내장 자료구조인 HashSet을 사용하였다
• key값인 nums[i]가 이미 존재한다면, 현재 방문한 요소의 인덱스와 최근에 저장된 인덱스의 차가 k보다 작거나 같은지 확인한다

 

• 내가 만든 자료구조는 메모리 사용량이 비효율적이다
  • key가 nums[i]로 잡히는데 그렇다는 것은, 가장 큰 요소 값이 10^9이면, bucket 배열의 길이를 10^9로 잡아야 한다 (유일성)
  • 그러면 만약 배열의 요소 갯수는 10개면 10개를 위해 나머지는 사용하지 않는다
    • 공간낭비가 극심하다

 

• Q1) HashMap은 어떻게 내부에서 capacity를 받지않고 추가할때마다 동적으로 늘어날까?
  
  • 초기에 생성자에서 capacity를 받을 수 있다
  • 받지 않을경우 기본값으로 설정된다
    • 기본 사이즈 값: 32
    • 기본 로드팩터 값: 0.75
  • 요소 추가시에 로드팩터 임계치가 넘을 경우, 리사이징 작업이 일어나면서 크기가 동적으로 늘어나는 것!

• Q2) Java의 HashMap은 들어오는 key값을 hash 함수의 응답값으로 key를 변환하여 사용한다
  그렇다면 음수값이 들어올 경우, 특정 양수와 충돌되면 해당 버킷에 값이 함께 포함될텐데, key의 유일성이 깨지는 것 아닌가?
  • 일단 HashMap은 key에 대한 hash 함수값이 같다면, 같은 버킷에 저장한다
  • 버킷의 각 요소들은 Node라는 클래스로 저장된다
    • Node는 Key, Value로 이루어져 있다
  • HashMap의 containsKey 메서드는 버킷의 각 Node를 순회하면서 Key값을 비교한다
  • 그러므로 유일성은 보장된다
  • 초기 버킷갯수를 capacity값으로 잡아도 된다

 

• 내장 자료구조가 아닌 직접 구현해야지라는 생각을 왜 했는지 모르겠다..
• 그래도 해시테이블의 해시함수를 왜 써야하는지 알게 되었다
• 또한 몰랐던 자바 내부구현을 알수 있었다