[프로그래머스] 전화번호 목록 (LV2 - JavaScript)

프로그래머스

1. 문제

 

제한사항

입출력 예

입출력 예 설명

2. 오답

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

    for (let i=0; i<phone_book.length; i++) {
        if (phone_book.filter((p,idx) => idx !== i && p.startsWith(phone_book[i])).length > 0) {
            return false;
        };
    }
    
    return true;
}

테스트 케이스는 모두 통과했지만, 효율성 테스트에서 탈락이다...😂😂

반복 횟수 줄일 수 있는 방법을 생각해 보자.

 

3. 정답 풀이

풀이 전략

• sort로 사전 순으로 배열을 정렬한다. (사전 순으로 정렬 시 접두사는 반드시 인접하게 정렬됨)

function solution(phone_book) {
    // 접두어 확인을 위해 사전 순으로 정렬
    phone_book.sort();
    
    // 배열을 순회하며 현재 값이 다음 값의 접두어인 경우 false 리턴 후 순회 종료
    for (let i=0; i<phone_book.length-1; i++) {
        if (phone_book[i+1].startsWith(phone_book[i])) return false;
    }
    
    return true;
}

 

오답에서 연산 횟수 줄이려고 sort하는 부분에서 아이디어가 떠올라 문제를 해결하게 되었다.

오답에서 왜 효율성 테스트를 통과하지 못했는지 궁금해 시간 복잡도를 찾아보게 되었다.

 

1. 정렬 = O(n log n) : n은 phone_book 배열의 길이(length)

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

 

2. for 루프 = n : 반복 횟수 phone_book 배열의 길이(length)

for (let i = 0; i < phone_book.length; i++) {}

 

3. filter = O(n * l)

phone_book.filter((p, idx) => idx !== i && p.startsWith(phone_book[i]))

• filter는 배열의 모든 요소를 순회하며 조건을 검사하므로 O(n)의 시간 소요
• 비교하는 문자열 길이를 l이라고 하면 최악의 경우 O(L)
• 따라서 둘의 시간 복잡도 중 최악을 계산하면 O(n * l)