해시(Hash) 개념

• 해시는 빠르게 데이터를 저장하고 검색할 수 있는 자료구조다.
• Key-Value형태로 데이터를 저장하는데, 자바스크립트에서는 객체(Object) 또는 Map을 이용할 수 있다.

프로그래머스 No.42577 전화번호 목록 문제를 해시 개념을 모르는채로 풀다보니 정확성은 나오는데 효율성에서 시간초과로 실패가 되었다.

---

❌ 처음에 내가 짰던 코드 (이중 반복문, O(N²))

처음에 내가 짰던 코드이다.

function solution(phone_book) {
    for (let i = 0; i < phone_book.length; i++) {
        for (let j = 0; j < phone_book.length; j++) {
            const a = phone_book[i];
            const b = phone_book[j];

            if ((a !== b) && ((a === b.slice(0, a.length)) || (b === a.slice(0, b.length)))) return false;          
        }
    }
    return true;
}

문제점: 이중 반복문을 사용했기 때문에 시간 복잡도 O(N2) -> 입력 크기가 커지면서 비효율적!

해시를 사용하면?

해시를 사용하면 검색을 빠르게 할 수 있어 효율적인 풀이가 가능하다.
접근 방법은 다음과 같다:

1. 모든 전화번호를 해시 테이블(객체)에 저장
   -> 빠르게 검색하기 위해!
2. 각 번호의 접두사가 이미 해시 테이블에 있는지 확인
   -> 존재하며 false 반환!

---

해시를 사용한 최적화된 코드(O(NM))

코드로 이해해보자.

function solution(phone_book) {
    const hash = {}; // 해시 테이블 생성

    // 1️⃣ 모든 번호를 해시 테이블에 저장
    for (const number of phone_book) {
        hash[number] = true; 
    }

    // 2️⃣ 각 번호의 접두사가 해시에 존재하는지 확인
    for (const number of phone_book) {
        let prefix = ""; // 접두사 초기화

        for (let i = 0; i < number.length - 1; i++) { // 마지막 글자는 제외
            prefix += number[i]; // 접두사 한 글자씩 추가

            if (hash[prefix]) { // 접두사가 이미 해시에 있으면 false
                return false;
            }
        }
    }

    return true; // 접두사가 없으면 true
}

---

🔍 코드 설명

1️⃣ 해시테이블 생성 및 전화번호 저장

const hash = {}; // 빈 해시 테이블 생성

for (const number of phone_book) {
	hash[number] = true;
}

• 전화번호를 해시 테이블에 저장해 빠른 검색을 가능하게 한다.
• 자바스크립트 객체(Object)를 활용하여 Key-Value 형태로 저장한다.

[펼쳐보기] 객체를 저장하는 법을 모른다면?

객체(Object)는 Key-Value(키-값) 쌍으로 데이터를 저장하는 자료구조이다.

객체에서 데이터를 저장하는 기본적인 방법은 크게 두 가지가 있다.

방법1. 점 표기법 (dot notation)

객체이름.키 = 값 형태로 저장!

const person = {}; // 빈 객체 생성
person.name = '지니'; // key를 'name'으로 저장! value를 '지니'로 저장!
person.age = '25'; // key를 'age'로 저장! vlue를 25로 저장!

이렇게 하였을 때, person 객체가 하면 결과가 {name: '지니', age:25} 로 출력되는 것을 확인할 수 있다.

또한 객체 key 값을 출력하면 다음과 같은 결과가 나온다.

console.log(person.name); // '지니'
console.log(person.age); // 25

---

방법2. 대괄호 표기법 (bracket notation)

const person = {}; // 빈 객체 생성
person['name'] = '지니'; // key를 'name'으로 저장! value를 '지니'로 저장!
person['age']  = 25; // key를 'age'로 저장! value를 25로 저장

객체이름['키'] = 값 의 형태로 저장하는 방법이다.

---

다시 문제 코드로 살펴보자.

for (const number of phone_book) {
        hash[number] = true; 
}

phone_book배열을 하나씩 돌면서 hash[번호] = true
-> 번호들을 true 값으로 먼저 저장을 해준다.

---

2️⃣ 접두사 검사

for (const number of phone_book) {
        let prefix = ""; // 접두사 초기화

        for (let i = 0; i < number.length - 1; i++) { // 마지막 글자는 제외
            prefix += number[i]; // 접두사 한 글자씩 추가

            if (hash[prefix]) { // 접두사가 이미 해시에 있으면 false
                return false;
            }
        }
    }

• 각 전화번호를 하나씩 가져와 한 글자씩 접두사를 만들어 간다.
• 만든 접두사가 해시 테이블에 존재한다면?
  -> 이미 저장된 전화번호 접두사임을 의미하므로 false 를 반환한다.

---

3️⃣ 접두사가 없을 경우 true 반환

return true;

• 모든 번호를 확인했는데 접두사가 발견되지 않으면 true 반환한다.

3. 접두사가 없다면 true 를 return 한다.

---

🔥 시간 복잡도 비교

• ❌ 이중 반복문 (내 코드) O(N²) -> (시간 초과 발생 🚨)
• ✅ 해시 테이블 활용 O(NM) -> (효율성 통과 ✅)

---

🎯 정리

1. 해시는 빠른 검색(O(1))이 가능한 구조
2. 전화번호를 해시 테이블에 저장하면 빠르게 검색 가능
3. 이중 반복문을 해시로 개선하면 효율성 통과