[JS] 전화번호 목록

 

 

난이도: Lv. 2

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

프로그래머스

 

 

알고리즘

1. 전화번호부를 String 자료형을 기준으로 오름차순 정렬한다.

2. 앞에 위치한 전화번호가 바로 뒤에 위치한 전화번호의 접두사인지 확인한다. 접두사일 경우 false를 반환한다.

 

 

코드

해시 사용

function solution(phone_book) {
    phone_book.sort();
    const hashMap = new Map();

    for (let i = 0; i < phone_book.length - 1; i++) {
        hashMap.set(phone_book[i], '');
        if (hashMap.has(phone_book[i + 1].substring(0, phone_book[i].length))) { return false; }
    }

    return true;
}

해시 미사용

function solution(phone_book) {
    phone_book.sort();

    for (let i = 0; i < phone_book.length - 1; i++) {
        if (phone_book[i] === phone_book[i + 1].substring(0, phone_book[i].length)) { return false; }
    }

    return true;
}

 

 

주저리

1트에는 테스트케이스는 전부 맞았는데 효율성 테스트 3, 4를 통과 못했었다. 시간복잡도가 O(n^2)이기 때문인 것 같았다. 애초에 정렬도 문자열을 기준으로 한 게 아니라 문자열의 길이를 기준으로 했다. 정렬된 배열의 원소를 기준으로 그 원소 뒤에 있는 모든 문자열을 검사했다. 접두사니까 길이가 짧은 문자열 순서대로 정렬해야 한다는 편견 때문이었다.

function solution(phone_book) {
    phone_book.sort((a, b) => a.length - b.length);

    for (let i = 0; i < phone_book.length - 1; i++) {
        const hashMap = new Map();
        hashMap.set(phone_book[i], 0);
        const prefixLen = phone_book[i].length;
        for (let j = i + 1; j < phone_book.length; j++) {
            if (hashMap.has(phone_book[j].substring(0, prefixLen))) { return false; }
        }
    }

    return true;
}

 

2트에는 문자열 기준으로 정렬해서 배열을 한 번만 순회하도록 했는데 바보같이 includes 써서 접두사가 아니고 단지 포함만 하고 있어도 false를 반환하도록 해서 테스트 케이스 13번을 틀렸다. 효율성 테스트는 모두 통과했다.

function solution(phone_book) {
    phone_book.sort();

    for (let i = 0; i < phone_book.length; i++) {
         if (phone_book[i + 1].includes(phone_book[i])) { return false; }
    }

    return true;
}

 

해시 쓸 때 Map 선언하는 건 반복문 안에 쓰던 밖에 쓰던 결과가 달라지지는 않는다. 질문하기에서 힌트를 보고 풀었는데 이게 굳이 해시 문제인가? 싶긴 했다. 왼쪽이 해시로 푼 거고 오른쪽이 해시 없이 푼 거다.