해시(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) -> 입력 크기가 커지면서 비효율적!
해시를 사용하면?
해시를 사용하면 검색을 빠르게 할 수 있어 효율적인 풀이가 가능하다.
접근 방법은 다음과 같다:
- 모든 전화번호를 해시 테이블(객체)에 저장
-> 빠르게 검색하기 위해! - 각 번호의 접두사가 이미 해시 테이블에 있는지 확인
-> 존재하며 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 반환한다.
- 접두사가 없다면 true 를 return 한다.
🔥 시간 복잡도 비교
- ❌ 이중 반복문 (내 코드) O(N²) -> (시간 초과 발생 🚨)
- ✅ 해시 테이블 활용 O(NM) -> (효율성 통과 ✅)
🎯 정리
- 해시는 빠른 검색(O(1))이 가능한 구조
- 전화번호를 해시 테이블에 저장하면 빠르게 검색 가능
- 이중 반복문을 해시로 개선하면 효율성 통과
세상을 이롭게 하는 프론트엔드 개발자 Jinny