[코딩테스트] 프로그래머스 - 전화번호 목록 Lv 2 (JS)

문제 설명

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

문제 풀이

먼저 phone_book 배열의 각 요소를 Map 객체의 Key로 지정한다.

Key: phoneNumber
Value: True

phone_book 배열의 각 요소를 순회하면서 요소를 1부터 요소 길이 -1까지를 순서대로 잘라보는데,
이때 잘라낸 번호가 Map 객체의 Key 값으로 있으면 해당 Map 요소가 현재 phone_book 요소의 접두사로 쓰인 것이므로 false를 반환한다.

모든 요소를 순회한 후 접두사로 쓰인 것을 못 찾았다면 true를 반환한다.

해시를 사용하지 않고 구현할 수도 있으나 잘라낸 번호를 phone_book 배열의 각 요소와 비교하기 위해 매번 전체 비교를 해야하므로 O(n²)의 시간 복잡도를 가지게 된다.

해시를 사용하면 get메서드의 시간복잡도 O(1)이므로 O(n)의 시간 복잡도를 가지게된다.

코드

function solution(phone_book) {
   let dict = {};
   phone_book.forEach(phoneNumber => dict[phoneNumber] = true);

   for(let phoneNumber of phone_book) {
    for(let i = 1; i < phoneNumber.length; i++) {
        const subPhoneNumber = phoneNumber.slice(0, i);
        if(dict[subPhoneNumber]) return false;
    }
   }
   return true;
}

function solution(phone_book) {
   let dict = new Map();
   phone_book.forEach(phoneNumber => dict[phoneNumber] = true);

   for(let phoneNumber of phone_book) {
    for(let i = 1; i < phoneNumber.length; i++) {
        const subPhoneNumber = phoneNumber.slice(0, i);
        if(dict[subPhoneNumber]) return false;
    }
   }
   return true;
}

function solution(phone_book) {
   let dict = new Map();
   phone_book.forEach(phoneNumber => dict.set(phoneNumber, true));

   for(let phoneNumber of phone_book) {
    for(let i = 1; i < phoneNumber.length; i++) {
        const subPhoneNumber = phoneNumber.slice(0, i);
        if(dict.get(subPhoneNumber)) return false;
    }
   }
   return true;
}

속도는 Map(get,set메서드 사용) > Map(대괄호 사용) > 객체 순으로 빨랐다.

사용한 자료구조

Hash Map

Map

사용한 메서드

Map.get(key)
Map.set(key, value)
String.slice(start, end)
start부터 end -1까지의 인덱스에 해당하는 문자열을 반환한다.
Array.forEach(callbackFn)
배열의 각 요소에 대해 콜백 함수를 실행한다.