[JavaScript/알고리즘] 전화번호 목록

프로그래머스

 

어떤 문자열이 리스트 내 다른 문자열의 접두어가 되는 경우 false, 그런 경우가 없다면 true를 출력하는 문제.

function solution(phone_book) {
    for (let i=0; i<phone_book.length; i++) {
        if (i === phone_book.length - 1) {
            break;
        }
        
        for (let j=i+1; j<phone_book.length; j++) {
            if (phone_book[j].split(phone_book[i])[0] === "" || phone_book[i].split(phone_book[j])[0] === "") {
                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 + 1].startsWith(phone_book[i])) {
            return false;
        }
    }
    
    return true;
}

 

정렬 후 다음 인덱스의 요소가 현재 인덱스의 요소를 접두어로서 쓰고 있는지 확인한다. 더욱이, split() 대신 startsWith() 메소드를 사용하여 더 직관적인 코드가 되었다.