Map, Set 그리고 해시맵 알고리즘

JavaScript에서 Map과 Set은 데이터 구조를 나타내는 두 가지 중요한 객체다.

각각은 고유한 용도와 특징을 가지고 있어, 이를 제대로 이해하고 사용하는 것은 효율적인 코드 작성에 도움이 된다.

1. Map

• Map 객체는 키-값 쌍을 저장하며, 키의 원본 삽입 순서를 기억한다.
• 어떤 값(객체와 기본 타입 값)도 키나 값으로 사용할 수 있다.

주요 메서드와 프로퍼티:

- set(key, value): Map 객체에 키-값 쌍을 추가한다.

- key(key): 키에 해당하는 값을 반환한다. 키가 존재하지 않으면 undefined 반환.

- has(key): Map 객체에 키가 존재하면 true, 아니면 false

- delete(key): 키에 해당하는 값 삭제

- clear(): 모든 요소를 제거

- size: Map 객체의 요소 개수 반환

const Map = new Map();

map.set('name', 'Alice');
map.set('age', 30);

console.log(map.get('name')); // Alice
console.log(map.has('age')); // true
console.log(map.size); // 2

map.delete('age');
console.log(map.has('age')); // false

map.clear();
console.log(map.xize); // 0

2. Set

• Set 객체는 자료형에 관계없이 유일한 값들만 저장한다.
• 이는 배열과 유사하지만 중복된 값을 허용하지 않는 차이가 있다.

주요 메서드와 프로퍼티:

- add(value): Set 객체에 값을 추가한다.

- has(value): 값이 Set 객체에 존재하면 true, 아니면 false

- delete(value): 값을 삭제

- clear(): 모든 요소를 제거

- size: Set 객체의 요소 개수를 반환

const set = new Set();

set.add(1);
set.add(2);
set.add(2); // 중복된 값

console.log(set.has(1)); // true
console.log(set.size); // 2

set.delete(2);
console.log(set.has(2)); // false

set.clear();
console.log(set.size); // 0

3. Map과 Set의 비교

1) 유사점

• 둘 다 삽입 순서가 유지된다.
• 둘 다 요소가 존재하는지 빠르게 검사할 수 있다.
• 둘 다 forEach 메서드를 사용하여 요소를 반복할 수 있다.

2) 차이점

저장 구조:

- Map은 키-값 쌍을 저장

- Set은 값만 저장(중복 허용 X)

용도:

- Map은 객체를 키-값 쌍으로 저장, 복잡한 데이터 구조 표현에 유용

- Set은 중복되지 않는 유일한 값을 저장하는 데 유용

메서드:

- Map은 키와 값을 모두 조작하는 메서드를 제공, get, set, has, delete 등의 메서드를 사용

- Set은 값만 조작하는 메서드를 제공, add, has, delete 등의 메서드 사용

4. 해시맵 알고리즘

1) 해시맵 정의

해시맵 알고리즘은 키-값 쌍을 저장하고, 키를 통해 값을 빠르게 검색, 삽입, 삭제 할 수 있는 데이터 구조다.

해시맵은 해시 함수를 사용하여 키를 해시값으로 변환하고, 이 해시값을 이용하여 데이터 저장소 내에서 값을 찾는 위치를 결정한다.

• 해시맵의 주요 특징은 다음과 같다.

2) 해시맵의 주요 특징

해시 함수(Hash Function):

- 임의의 크기를 가진 입력 데이터를 고정된 크기의 해시값으로 변환하는 함수다.

- 좋은 해시 함수는 키를 균일하게 분포, 충돌을 최소화한다.

충돌(Collision):

- 서로 다른 키들이 동일한 해시값을 가질 때 발생한다.

- 충돌을 해결하기 위해 여러 가지 방법이 사용된다.

충돌 해결 방법:

- 체이닝(Chaining): 해시값이 같은 키-값 쌍을 연결 리스트로 저장한다.

- 오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 빈 슬롯을 찾아 저장. 선형 탐사, 이차 탐사, 이중 해싱 등의 기법이 있다.

3) 해시맵의 시간 복잡도

• 평균 시간 복잡도: 해시맵의 평균 검색, 삽입, 삭제 시간 복잡도는 O(1)이다.
• 최악의 시간 복잡도: 해시 함수가 충돌을 많이 발생시키면, 최악의 경우 O(n)의 시간 복잡도를 가진다.

4) 해시맵의 활용

• 해시맵은 데이터의 빠른 검색, 삽입, 삭제가 필요한 상황에서 매우 유용하다.
• 전화번호부, 캐싱 시스템, 데이터베이스 인덱싱 등 다양한 응용 분야에서 사용된다.

5. Set과 Map을 활용한 해시맵 알고리즘

1) 문제 설명

• 주어진 배열 phone_book에서 어떤 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제이다.
• Map과 Set을 활용하여 해당 문제를 풀어낸다.

2) 알고리즘 해결 단계

- Map을 사용하여 각 전화번호를 저장

- Set을 사용하여 이미 처리된 접두어를 저장

- 각 전화번호의 모든 접두어를 확인하여, 접두어가 이미 Map에 존재하거나 Set에 존재하는지 검사

- 존재하면 false, 그렇지 않다면 모든 검사 후 true 반환

3) 구현

function solution(phone_book) {
    const phoneMap = new Map();
    const prefixSet = new Set();

    // 모든 전화번호를 해시맵에 저장
    for (let phone of phone_book) {
        phoneMap.set(phone, true);
    }

    // 각 전화번호에 대해 접두어가 다른 전화번호에 있는지 확인
    for (let phone of phone_book) {
        let prefix = '';
        for (let i = 0; i < phone.length; i++) {
            prefix += phone[i];
            if (i < phone.length - 1) {
                if (phoneMap.has(prefix) || prefixSet.has(prefix)) {
                    return false;
                }
                prefixSet.add(prefix);
            }
        }
    }

    return true;
}

// 테스트 케이스
const phone_book1 = ["119", "97674223", "1195524421"];
const phone_book2 = ["123", "456", "789"];

console.log(solution(phone_book1)); // false
console.log(solution(phone_book2)); // true

4) 시간 복잡도

• Map과 Set을 사용한 위의 알고리즘 시간 복잡도는 O(n * k)이다.
• n은 전화번호의 수, k는 전화번호의 최대 길이이다.
• 각 전화번호에 대해 최대 k번의 접두어 검사를 수행하므로, 전체 시간 복잡도가 O(n * k)가 되는 것이다.

5) Map, Set의 사용 이유?

모든 전화번호 저장: 모든 전화번호를 Map에 저장하여, 특정 전화번호가 존재하는지 빠르게 확인 가능

키-값 쌍으로 저장: 전화번호를 키로 Map에 저장하고, 값을 true로 설정하여 존재 여부를 쉽게 확인 가능

중복된 접두어 추적: Set으로 각 전화번호의 접두어를 추적하여 중복된 접두어가 존재하는지 확인

빠른 접두어 확인: Set을 사용하여 접두어가 이미 확인된 접두어인지 빠르게 검사가 가능

• Map을 사용하여 전화번호의 존재 여부를 빠르게 확인
• Set을 사용하여 중복된 접두어를 효율적으로 관리