42577. 전화번호 목록

프로그래머스 42577번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 스쿨

풀이

아이디어

phone_book의 최대 길이가 1,000,000이기 때문에 이중 for문으로 모든 쌍을 비교하면 시간 초과가 발생할 것이다. 그래서 Set을 활용해서 접두어 존재 여부를 O(1)에 확인하는 방식을 사용했다.

1. 모든 전화번호의 접두어들(자기 자신 제외)을 Set에 저장한다.
2. 전화번호 목록을 다시 순회하면서, 해당 번호가 Set에 있는지 확인한다.
3. Set에 있다면 그 번호는 다른 번호의 접두어라는 의미이므로 false를 반환한다.

코드

function solution(phone_book) {
    const numberSet = new Set();
    for (const number of phone_book) {
        // 같은 전화번호가 중복해서 들어있지 않으므로 끝번호를 제외한 부분문자열만 구해준다.
        for (let len = 1; len < number.length; len++) {
            numberSet.add(number.substring(0, len))
        }
    }

    for (const number of phone_book) {
        if (numberSet.has(number)) {
            return false;
        }
    }

    return true;
}