꒰ྀི 16. 프로그래머스:: 전화번호 목록

사이트 문제도 첨부되지 않고 저작권 걸리는게 무서워 프로그래머스로 회귀했다.

 

 

문제 요약

 

전화번호부에 적힌 전화번호 중 한 번호가 다른 번호의 접두어인 경우가 있는지 확인

해시 테이블이 권장되는 문제이다.

 

해시테이블

평균적으로 O(1)의 시간 복잡도를 갖기 때문에 빠른 검색에 용이하다.
따라서 접두어를 확인하는 데 효율적이다.

 

접근 방법

1. 모든 전화번호를 해시 테이블에 저장한다.
2. 각 전화번호의 접두어가 해시 테이블에 존재하는지 확인한다.

 

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

    for (const phone of phone_book) {
        phoneMap.set(phone, true);
    }

    for (const phone of phone_book) {
        for (let i = 1; i < phone.length; i++) {
            const prefix = phone.slice(0, i);
            if (phoneMap.has(prefix)) {
                return false;
            }
        }
    }

    return true;
}

 

다른 사람의 풀이

function solution(phoneBook) {
    return !phoneBook.sort().some((t, i) => {
        if (i === phoneBook.length - 1) return false;
        return phoneBook[i + 1].startsWith(phoneBook[i]);
    });
}

 

어떻게 이렇게 깔끔해지는걸까?

 

주어진 전화번호 목록을 정렬하고, 접두어인지 확인한다.

특히 startsWith는 아예 처음 보는 메서드다.

---

startsWith

JavaScript의 문자열 메서드다.
문자열이 특정 문자열로 시작하는지 확인하는 데 사용된다.
특정 문자열로 시작하면 true, 아니라면 false를 반환한다.

 

let str = "Hello, world!";

console.log(str.startsWith("Hello")); // true

 

해시 테이블을 이용한 내 코드는 공간 효율성은 약간 부족한 반면 시간적 면에서 뛰어나다.

다른 사람의 코드는 정렬이 필요하기 때문에 입력의 크기가 커질수록 시간 소모가 증가한다.