[PRO] 프로그래머스 Lv.2 전화번호 목록 (Javascript)

문제

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

프로그래머스

 

문제 해석

접근 방법

전화번호 목록 중에서 어떤 전화번호가 다른 전화번호의 접두사가 되는 경우가 있는지 찾는 문제입니다.

 

문제에서 전화번호 목록의 길이가 최대 1,000,000이라고 주어졌습니다. 이에 따라 모든 문자열을 1:1로 직접 비교할 경우 효율성이 떨어져 시간초과가 일어날 수 있습니다.

 

따라서 Set 객체를 사용해 이전에 탐색한 정보를 저장하는 방식으로 구현해야 합니다.

 

풀이 과정

접두사를 체크할 때 자신보다 길이가 짧은 번호만 탐색하도록 주어진 배열 phoneBook을 길이 오름차순으로 정렬합니다.

 

그리고 phoneBook을 순회하며 set을 탐색해 접두사 포함 여부를 판별합니다. 이 때, 길이가 같은 문자열끼리 비교하는 불필요한 탐색을 방지하기 위해 탐색 중인 번호의 길이가 변경되는 시점에 이전에 탐색했던 번호들을 set에 추가했습니다.

 

마지막 번호까지 탐색한 후에 접두사가 포함되어 있지 않으면 true, 그렇지 않으면 false를 반환하면 됩니다.

 

 

전체 코드

function solution(phoneBook) {
    phoneBook.sort((a, b) => a.length - b.length);
    let set = new Set(),
        s = 0;
    while (s < phoneBook.length) {
        let len = phoneBook[s].length;
        for (let e = s; e < phoneBook.length; e++) {
            if (len !== phoneBook[e].length) {
                for (let i = s; i < e; i++) {
                    set.set(phoneBook[i]);
                }
                s = e;
                break;
            } else {
                for (let i = 1; i < len; i++) {
                    if (set.has(phoneBook[e].slice(0, i))) return false;
                }
                if (e === phoneBook.length - 1) return true;
            }
        }
    }
}

 

회고

• 반복문이 중첩되는 경우 변수의 갱신 여부와 갱신 시점을 정확하게 파악한 후 코드를 작성해야 오답을 줄일 수 있다.