전화번호 목록

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

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.
입출력 예제
phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false
입출력 예 설명
입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

// 해시를 이용한 방법(문제 의도인 것 같음)
// 먼저 set으로 집합을 만든 다음, 
// 개별 전화번호에 대해서 첫 자부터 length -1자까지 슬라이스해 가면서 hash에 있는지 확인하는 방법
// function solution(phone_book) {
//     // 먼저 집합으로 만듦
//     const hash = new Set(phone_book);
    
//     for(const phoneNo of phone_book) {
//         for(let i = 0; i < phoneNo.length; i++) {
//             const prefix = phoneNo.slice(0,i);
//             if(hash.has(prefix)) return false;
//         }
//     }
//     return true;
// }

// 통과는 했지만 위 방법은 O(n×m) 루프에 slice까지 O(m)이므로 총 O(n×m²). 아래의 방법이 더 효과적인듯


function solution(phone_book) {
    // 먼저 소팅
    // 정렬하면 접두어 관계에 있는 번호들이 인접하게 배치됨
    phone_book.sort();
    
    // 현재 번호가 다음 번호의 접두어인지만 확인8
    // for(let i = 0; i < phone_book.length; i++) {   아래에서 +1해주기 때문에 여기서 -1 해줘야 함
    for(let i = 0; i < phone_book.length - 1; i++) {
        if(phone_book[i + 1].startsWith(phone_book[i])) 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;
// }



// function solution(phone_book) {
    
//     // 순회하면서 ' '를 기준으로 나눈 뒤 다시 붙이기
    
//     //     phone_book.forEach((el) => el.split(' ').join(''))
//     //     console.log(phone_book)
    
//     const obj = {};
//     phone_book.forEach((el) => obj[el] = 1)
//     // console.log(obj)
    
//     // 그 다음 어떻게 하려고
//     // 오브젝트의 키를 순회시키면서
//     // 배열의 원소에 includes()가 있는지 확인하기 <- 이렇게 풀면 안됨. startsWith
    
//     for(const key of Object.keys(obj)) {
//        for(let i = 0; i < phone_book.length; i++) {

//            // 아래처럼 풀면 자기 자신을 포함하게 되어서 항상 false반환함
//            // 게다가 O(n2)이 돼 버려서 시간 초과됨
//            // if(phone_book[i].includes(key)) {
//            //     return false;
//            // }
           
//            // 자기 자신이 아니면서 && 접두어인 경우
//            if(key !== phone_book[i] && phone_book[i].startsWith(key)) {
//                return false;
//            }
           
//        }
//     }
    
//     var answer = true;
    
//     return answer;
// }

 

 

맨 아래가 원래 나의 풀이었음. 나의 사고방식의 문제는 이랬다.

 

핵심 문제점 정리:
문제원인접두어 → 포함문제를 정확히 파악하지 못함불필요한 obj자료구조 사용 목적이 불명확자기 자신 비교엣지 케이스를 고려하지 않음O(n²)효율성보다 "일단 동작"에 집중
개선된 사고 프로세스:

문제 정의: "접두어 관계 찾기" → startsWith 필요
자료구조 선택: 해시는 "이 접두어가 존재하는가?" O(1) 조회용
엣지 케이스: 자기 자신은 제외해야 함
효율성: 정렬하면 인접 비교만으로 충분

다음번엔 **"이 자료구조를 왜 쓰는가?"**를 먼저 생각