프로그래머스 : 전화번호 목록-javascript(해시)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

전화번호 목록
문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.

나의 틀린 코드 

효율성의 문제가 있었다. 왜냐? 해시를 이용하지 않았거덩요,,, 

 

function solution(phone_book) {
    for(let i=0; i<phone_book.length; i++){
        let check = phone_book[i];
        let len = phone_book[i].length;
        for(let j=0; j<phone_book.length; j++){
            if(j === i) continue; 
            else{
                if(phone_book[j].slice(0,len) === check){
                    return false; 
                }
            }
        }
    }
    return true; 
}

정답 풀이 힌트 

1. 해시 생성 

2. 해시 값 채워넣기 

3. 주어진 배열 모든 값에서 space 없애는 정리 

4. 정리한 배열을 반복문 돌리면서 하나의 전화번호의 각 문자를 뜯어보면서 그게 해시 key 존재하는지 확인한다. 

이 예시에서 설명 해보겠음

 

5. 존재한다면 false(뜯어보고 있는 문자를 제외해서 존재), 존재하지 않는다면 true

정답 풀이 코드 

function solution(phone_book) {
   const hashMap = {}; //1. 해시 생성
    for(let phoneNumber of phone_book){
        hashMap[phoneNumber] = 1; //2. 해시 값 채워넣기 
    }
    for(let phoneNumber of phone_book){
        let temp = ""; 
        const phoneNumberWithoutSpace = phoneNumber.replace(/\s/g,""); //3. 각 전화번호 공백 없애기
        for(let number of phoneNumberWithoutSpace){
            temp += number; //4. 각 전화번호 문자 뜯어보기
            if(hashMap[temp] && temp !== phoneNumberWithoutSpace){
                return false; //5. 뜯어본 문자가 해시에 키로 존재하는지 확인하기 
            }
        }
    }
    return true; 
}

의사 코드 추가 

function solution(phone_book) {
   const hashMap = {}; //
    for(let phoneNumber of phone_book){
        hashMap[phoneNumber] = 1;
    }
    for(let phoneNumber of phone_book){
        let temp = ""; 
        const phoneNumberWithoutSpace = phoneNumber.replace(/\s/g,"");
        for(let number of phoneNumberWithoutSpace){
            temp += number;
            if(hashMap[temp] && temp !== phoneNumberWithoutSpace){
                return false; 
            }
        }
    }
    return true; 
}