이전 글에서 다루지 못한 기술적 개념을 찾으세요:

**개인 홈페이지:**我要学编程(ಥ_ಥ)-CSDN 블로그

소속 전문: 데이터 구조 (Java 버전)

이전 글에서는 이진 탐색 트리, 맵과 세트의 기본 개념, 해시 테이블의 충돌 해결 방식 등을 다뤘습니다. 데이터 구조에서 맵과 세트 (상) - CSDN 블로그

이제 나머지 주제를 살펴보겠습니다.

목차

충돌 해결 - 클로즈드 해싱 충돌 해결 - 오픈 해싱/해시 버킷 수동으로 해시 테이블 구현 해시 테이블과 자바 클래스의 관계 맵과 세트 관련 연습 문제

136. 한 번만 나타나는 숫자
137. 랜덤 연결 리스트 복사
138. 보석과 돌
139. 상위 K개의 빈도 단어

충돌 해결 - 클로즈드 해싱

클로즈드 해싱(오픈 주소법): 해시 충돌이 발생했을 때, 해시 테이블이 가득 차지 않았다면 충돌 위치의 "다음" 빈 위치에 키를 저장할 수 있습니다. 다음 빈 위치를 찾는 방법은?

1. 선형 탐색

예를 들어, 44를 삽입해야 할 때 해시 함수 (요소 % 해시 테이블 길이)로 해시 주소를 계산합니다. 인덱스 4에 위치해야 하지만 이미 4가 존재하므로 해시 충돌이 발생합니다. 선형 탐색: 충돌 위치부터 차례로 뒤로 탐색하여 빈 위치를 찾습니다.

해시 함수로 삽입할 요소의 위치를 계산합니다. 해당 위치에 요소가 없으면 새 요소를 삽입하고, 있으면 선형 탐색으로 다음 빈 위치를 찾아 삽입합니다. 위 그림의 8 인덱스 위치를 참고하세요.

주의사항:

클로즈드 해싱으로 해시 충돌을 처리할 때, 기존 요소를 물리적으로 삭제하면 다른 요소의 검색에 영향을 줄 수 있습니다. 예를 들어 4를 삭제하면 44의 검색에 문제가 생길 수 있습니다. 따라서 선형 탐색은 가상 삭제 방식을 사용합니다. 노드로 요소를 표현하고, 부울형 변수로 요소의 존재 여부를 표시합니다.

2. 이차 탐색

선형 탐색의 단점은 충돌 데이터가 한 곳에 모여 탐색 시간이 증가하는 것입니다. 이차 탐색은 다음 빈 위치를 H=(Ho+i²)% m 또는 H=(Ho-2²)% m 방식으로 계산합니다. Ho는 해시 함수로 계산된 원래 위치, m은 테이블 크기입니다. 44를 삽입할 때 충돌을 해결하는 경우:

H=(Ho+i²)% m → H = (4 + 1^2) % 10 = 5 → 이미 요소 존재 → 계속 탐색; H=(Ho+i²)% m → H = (4 + 2^2) % 10 = 8 → 빈 위치이므로 삽입.

주의사항:

연구에 따르면, 테이블 길이가 소수이고 로드 팩터 a가 0.5 이하일 때, 새로운 항목은 반드시 삽입 가능하며, 어떤 위치도 두 번 탐색되지 않습니다. 따라서 테이블의 절반 이상이 비어 있으면 테이블이 가득 차는 경우를 고려할 필요가 없습니다. 하지만 삽입 시 로드 팩터가 0.5를 초과하면 확장해야 합니다. 이는 공간을 시간으로 교환하는 방식입니다.

충돌 해결 - 오픈 해싱/해시 버킷

오픈 해싱(체이닝)은 키 집합을 해시 함수로 계산한 후, 동일한 해시 주소를 가진 키를 버킷으로 분류합니다. 각 버킷은 단일 연결 리스트로 연결되며, 각 리스트의 헤드 노드는 해시 테이블에 저장됩니다. 간단히 말해 배열과 여러 연결 리스트의 결합입니다. 충돌이 발생하더라도 동일한 인덱스에 저장할 수 있습니다.

오픈 해싱은 대규모 집합의 검색 문제를 소규모 집합의 검색으로 변환합니다. 하지만 연결 리스트가 길어지면 검색 시간 복잡도가 O(N)이 됩니다. 이를 방지하기 위해 각 배열 요소는 새로운 해시 테이블이 되며, 연결 리스트는 탐색 트리로 변환됩니다.

수동으로 해시 테이블 구현

아이디어: 배열과 여러 연결 리스트의 삽입, 수정, 검색을 구현합니다.

준비 코드:

    // 노드
    private static class Element {
        private int key;
        private int value;
        public Element next;

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

    private Element[] table;
    private int count; // 현재 데이터 개수
    private static final double LOAD_FACTOR = 0.75; // 로드 팩터
    private static final int DEFAULT_SIZE = 8; // 기본 버킷 크기

    // 해시 테이블 생성자
    public HashTable() {
        table = new Element[DEFAULT_SIZE];
    }

    // 로드 팩터 계산
    private double getLoadFactor() {
        return count * 1.0 / table.length;
    }

요소 추가/수정:

해시 함수로 인덱스를 계산하여 삽입 위치를 찾고, 헤드 삽입 방식을 사용합니다.

코드 구현:

    public int put(int key, int value) {
        int index = key % table.length;
        // 이미 존재하는 노드인지 확인
        Element current = table[index];
        while (current != null) {
            if (current.key == key) {
                current.value = value;
                return value;
            }
            current = current.next;
        }
        // 로드 팩터가 기준을 초과하면 확장
        if (getLoadFactor() >= LOAD_FACTOR) {
            resize();
        }
        // 헤드 삽입 방식으로 연결 리스트 생성
        Element node = new Element(key, value);
        node.next = table[index];
        table[index] = node;
        count++;
        return value;
    }

해시 테이블 확장:

새로운 배열을 생성하고 기존 배열의 요소를 재해시하여 삽입합니다.

코드 구현:

    private void resize() {
        // 직접 2배 확장 불가, 요소 위치 변경 가능성 있음
        // table = Arrays.copyOf(table, 2*table.length);

        // 새로운 배열 생성
        Element[] newTable = new Element[2*table.length];
        // 모든 요소 재해시
        for (int i = 0; i < table.length; i++) {
            Element current = table[i];
            while (current != null) {
                int index = current.key % newTable.length;
                Element newNode = new Element(current.key, current.value);
                newNode.next = newTable[index];
                newTable[index] = newNode;
                current = current.next;
            }
        }
        table = newTable;
    }

주의사항:

1. 2배 확장 불가, 요소가 올바른 위치에 있지 않을 수 있음
2. 반복 종료 조건을 size로 설정하지 않음, size는 요소 개수를 나타내지만 모든 요소를 포함하지 않을 수 있음

요소 검색:

직접 반복하여 검색합니다.

코드 구현:

    public int get(int key) {
        Element current = table[key % table.length];
        while (current != null) {
            if (current.key == key) {
                return current.value;
            }
            current = current.next;
        }
        return -1;
    }

해시 테이블은 충돌을 방지하기 위해 노력하지만, 실제 사용 시 충돌률은 낮고, 각 버킷의 연결 리스트 길이는 일정하므로 일반적으로 삽입/삭제/검색 시간 복잡도는 O(1)입니다.

해시 테이블과 자바 클래스의 관계

1. HashMap과 HashSet은 자바에서 해시 테이블로 구현된 맵과 세트입니다.
2. 자바는 해시 버킷 방식으로 충돌을 해결합니다.
3. 충돌 연결 리스트 길이가 일정 값 이상이 되면 연결 리스트를 이진 탐색 트리(레드블랙 트리)로 변환합니다. 이 값은 8이며, 해시 테이블 길이가 64 이상이어야 합니다.
4. 자바에서 해시 값을 계산할 때는 클래스의 hashCode 메서드를 호출하고, 키의 동등성 비교는 equals 메서드를 사용합니다. 따라서 사용자 정의 클래스를 HashMap의 키나 HashSet의 값으로 사용할 경우 hashCode와 equals 메서드를 재정의해야 하며, equals가 같은 객체는 hashCode도 동일해야 합니다.

맵과 세트 관련 연습 문제

136. 한 번만 나타나는 숫자

문제:

비어 있지 않은 정수 배열 nums가 주어집니다. 다른 요소는 모두 두 번 나타나지만, 하나의 요소만 한 번 나타납니다. 그 요소를 찾아내세요.

이 문제를 선형 시간 복잡도로 해결해야 하며, 상수 추가 공간만 사용해야 합니다.

예시 1:

<strong>입력:</strong> nums = [2,2,1]
<strong>출력:</strong> 1

예시 2:

<strong>입력:</strong> nums = [4,1,2,1,2]
<strong>출력:</strong> 4

예시 3:

<strong>입력:</strong> nums = [1]
<strong>출력:</strong> 1

참고:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 다른 요소는 모두 두 번 나타납니다.

아이디어 1: 가장 간단하고 효과적인 방법은 XOR 사용입니다. XOR 규칙은 이진 비트에서 동일하면 0, 다르면 1입니다. 따라서 남은 단독 요소를 찾을 수 있습니다.

코드 구현:

class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
}

아이디어 2: 중복 제거 아이디어: 해당 요소가 없으면 삽입하고, 있으면 삭제합니다. 여기서는 Set을 사용합니다.

코드 구현:

class Solution {
public int singleNumber(int[] nums) {
Set set = new HashSet<>();
for (int num : nums) {
if (!set.contains(num)) {
set.add(num);
} else {
set.remove(num);
}
}
return set.iterator().next();
}
}

138. 랜덤 연결 리스트 복사

문제:

길이가 n인 연결 리스트가 주어집니다. 각 노드는 추가로 랜덤 포인터를 포함합니다. 이 포인터는 연결 리스트의 어떤 노드나 null을 가리킬 수 있습니다.

이 연결 리스트의 깊은 복사를 생성해야 합니다. 깊은 복사는 n개의 새로운 노드로 구성되어야 하며, 각 새 노드의 값은 원래 노드의 값으로 설정되어야 합니다. 새 노드의 next 및 random 포인터는 복사된 연결 리스트의 새 노드를 가리켜야 하며, 원래 연결 리스트와 복사된 연결 리스트의 포인터가 동일한 연결 리스트 상태를 나타내야 합니다. 복사된 연결 리스트의 포인터는 원래 연결 리스트의 노드를 가리켜서는 안 됩니다.

예를 들어, 원래 연결 리스트에 X와 Y 두 노드가 있고, X.random --> Y라면, 복사된 연결 리스트의 x와 y 노드도 x.random --> y가 되어야 합니다.

복사된 연결 리스트의 헤드 노드를 반환하세요.

입력/출력은 n개의 노드로 구성된 연결 리스트로 표현됩니다. 각 노드는 [val, random_index]로 표현됩니다:

• val: Node.val을 나타내는 정수입니다.
• random_index: 랜덤 포인터가 가리키는 노드 인덱스(0~n-1 범위)입니다. 아무 노드도 가리키지 않으면 null입니다.

당신의 코드는 원래 연결 리스트의 헤드 노드만 입력으로 받습니다.

예시 1:

<strong>입력:</strong> head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
<strong>출력:</strong> [[7,null],[13,0],[11,4],[10,2],[1,0]]

예시 2:

<strong>입력:</strong> head = [[1,1],[2,1]]
<strong>출력:</strong> [[1,1],[2,1]]

예시 3:

<strong>입력:</strong> head = [[3,null],[3,0],[3,null]]
<strong>출력:</strong> [[3,null],[3,0],[3,null]]

참고:

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random은 null 또는 연결 리스트의 노드를 가리킬 수 있습니다.

아이디어 1: 해시 테이블 사용. 원래 연결 리스트와 새로운 연결 리스트의 관계를 키-값으로 매핑합니다.

코드 구현:

class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Map map = new HashMap<>();
Node current = head;
// 원래 연결 리스트와 새로운 연결 리스트의 관계 설정
while (current != null) {
map.put(current, new Node(current.val));
current = current.next;
}
// 새로운 연결 리스트의 next 및 random 값 업데이트
current = head;
while (current != null) {
// 아래 코드는 얕은 복사이므로 사용 불가
// map.get(current).next = current.next;
// map.get(current).random = current.random;

// 새로운 연결 리스트의 노드를 가리켜야 함
map.get(current).next = map.get(current.next);
map.get(current).random = map.get(current.random);
current = current.next;
}
return map.get(head);
}
}

아이디어 2: 전통적인 연결 리스트 생성 방식. 이 방법은 전문가만이 떠올릴 수 있습니다. 원래 연결 리스트에 새로운 연결 리스트를 붙입니다. 예: 원래 노드1 -> 새로운 노드1 -> 원래 노드2 -> 새로운 노드2 -> ... 이렇게 next 값을 설정합니다. 이후 원래 연결 리스트를 순회하여 random 값을 업데이트하고, 마지막으로 연결 리스트를 분리합니다.

주의사항: 동시에 연결 리스트를 생성하면서 random 값을 업데이트하면 안 됩니다. 왜냐하면 새로운 연결 리스트의 random 값이 아직 생성되지 않았기 때문입니다.

코드 구현:

class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 새로운 연결 리스트 생성
Node current = head;
while (current != null) {
Node temp = new Node(current.val);
// 원래 노드 뒤에 새로운 노드 삽입
temp.next = current.next;
current.next = temp;
// 원래 노드의 다음을 건너뛰어 다음 원래 노드로 이동
current = current.next.next;
}
// random 값 업데이트
current = head;
while (current != null) {
if (current.random != null) {
// 새로운 노드의 random 값은 원래 노드의 random의 다음 노드
current.next.random = current.random.next;
}
current = current.next.next;
}
// 원래 연결 리스트 분리
current = head;
Node newHead = current.next;
Node newCurrent = newHead;
while (current != null && current.next != null) {
// 원래 연결 리스트를 복원하기 위해 다음 노드를 건너뜀
current.next = current.next.next;
newCurrent.next = newCurrent.next == null ? null : newCurrent.next.next;
current = current.next;
newCurrent = newCurrent.next;
}
return newHead;
}
}

결론: 해시 테이블을 사용하지 않으면 난이도가 급격히 증가합니다. 먼저 어떻게 처리할지 알아야 하며, 세부 사항도 많이 고려해야 합니다.

771. 보석과 돌

문제:

문자열 jewels는 보석의 종류를 나타내고, 다른 문자열 stones는 소유한 돌을 나타냅니다. stones의 각 문자는 소유한 돌의 종류를 나타냅니다. 소유한 돌 중 보석의 수를 알아야 합니다.

알파벳은 대소문자를 구분하므로 "a"와 "A"는 서로 다른 종류의 돌입니다.

예시 1:

<strong>입력:</strong> jewels = "aA", stones = "aAAbbbb"
<strong>출력:</strong> 3

예시 2:

<strong>입력:</strong> jewels = "z", stones = "ZZ"
<strong>출력:</strong> 0<strong>
</strong>

참고:

• 1 <= jewels.length, stones.length <= 50
• jewels와 stones는 영문자만 포함합니다.
• jewels의 모든 문자는 유일합니다.

아이디어 1: 이중 루프로 보석을 순회하고, 돌을 순회하여 보석 개수를 세는 방법입니다.

아이디어 2: Set에 보석을 넣고, 돌을 순회하여 보석 개수를 세는 방법입니다.

코드 구현:

class Solution {
public int numJewelsInStones(String jewels, String stones) {
// 보석을 Set에 저장
Set set = new HashSet<>();
for (char jewel : jewels.toCharArray()) {
set.add(jewel);
}
int count = 0;
for (char stone : stones.toCharArray()) {
if (set.contains(stone)) {
count++;
}
}
return count;
}
}

692. 상위 K개의 빈도 단어

문제:

단어 목록 words와 정수 k가 주어집니다. 상위 k개의 빈도가 높은 단어를 반환하세요.

반환 결과는 단어의 빈도가 높은 순서로 정렬되어야 합니다. 동일한 빈도를 가진 단어는 사전 순으로 정렬되어야 합니다.

예시 1:

<strong>입력:</strong> words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
<strong>출력:</strong> ["i", "love"]
<strong>설명:</strong> "i"와 "love"는 빈도가 가장 높은 두 단어로, 각각 2회 나타납니다. 알파벳 순서에서 "i"가 "love"보다 앞섭니다.

예시 2:

<strong>입력:</strong> ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
<strong>출력:</strong> ["the", "is", "sunny", "day"]
<strong>설명:</strong> "the", "is", "sunny", "day"는 빈도가 높은 네 단어로, 빈도는 각각 4, 3, 2, 1회입니다.

참고:

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i]는 소문자 알파벳으로 구성됩니다.
• k의 범위는 [1, <strong>다른</strong> words[i]의 개수]입니다.

아이디어: 단어 목록을 순회하여 각 단어의 빈도를 통계 내고, 작은 루트 힙을 사용하여 상위 k개 요소를 저장합니다. 마지막으로 힙의 요소를 리스트에 삽입하고 역순으로 정렬합니다.

코드 구현:

class Solution {
public List topKFrequent(String[] words, int k) {
List result = new ArrayList<>();
// 각 단어의 빈도 통계
Map frequencyMap = new HashMap<>();
for (String word : words) {
frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);
}
// 작은 루트 힙 생성
PriorityQueue> minHeap = new PriorityQueue<>(
(a, b) -> {
if (!a.getValue().equals(b.getValue())) {
return a.getValue() - b.getValue();
} else {
return b.getKey().compareTo(a.getKey());
}
}
);
for (Map.Entry entry : frequencyMap.entrySet()) {
if (minHeap.size() < k) {
minHeap.offer(entry);
} else {
Map.Entry top = minHeap.peek();
if (top.getValue() < entry.getValue() ||
(top.getValue().equals(entry.getValue()) && top.getKey().compareTo(entry.getKey()) > 0)) {
minHeap.poll();
minHeap.offer(entry);
}
}
}
// 결과 리스트에 삽입
while (!minHeap.isEmpty()) {
result.add(minHeap.poll().getKey());
}
Collections.reverse(result);
return result;
}
}

주의사항: 사전 순서 비교 시, o2.getKey().compareTo(o1.getKey())를 사용해야 합니다. 아래 그림 참고:

이로 인해 빈도가 동일한 단어는 사전 순으로 큰 루트 힙을 구성해야 합니다.

주의사항: Arrays는 배열을 조작하는 클래스이고, Collections는 집합을 조작하는 클래스입니다.

이제 데이터 구조에서 맵과 세트 (하) 학습은 여기까지입니다. 다음에 다시 함께 학습해요!