D+31 Lv2 전화번호 목록 js

문제

해시문제라고 적혀있었는데, 해시보다 배열로 푸는게 더 빠름..

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

구조대 : 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입니다.

(4) O 기억할 풀이 -!!

function solution(phoneBook) {
    return !phoneBook.sort().some((t,i)=> {
        if(i === phoneBook.length -1) return false;

        return phoneBook[i+1].startsWith(t);        
    })
}

(3) 클로드의 틀린 풀이 다른 풀이 - hash로 푼 버전

이것을 기억해야 한다. 기억해야하는 것 맨 위로 올려둠 ㅎㅎ
클로드 짱...
확실히 hash로 풀면 엄청난 속도로 성능 테스트가 끝난다.
근데 코드를 보니 한 글자씩 보고있네..?! 클로드가 잘못 짜준 거였다..

function solution(phone_book) {
    const hash = new Set(phone_book);
    
    for (let number of phone_book) {
        // 현재 번호의 모든 가능한 접두어 확인
        for (let i = 1; i < number.length; i++) {
            const prefix = number.slice(0, i);
            // 접두어가 해시맵에 있다면 false 반환
            if (hash.has(prefix)) {
                return false;
            }
        }
    }
    return true;
}

내 풀이

(1) 일단 반복문

처음 시간초과 될 것 같긴 했지만,, 일단 반복문으로 풀어봤음
해시 개념만 좀 읽은 정도여서 풀이 익숙해지자

function solution(phone_book) {
    let answer = true;
    const arr= phone_book.sort((a,b)=> a-b)
    for(i=0; i<arr.length; i++){
        for(j=i+1; j<arr.length; j++){
            if(arr[j].startsWith(arr[i])){
                answer = false
                return answer
            }
        }
    }
    return answer;
}

(2) 수정한 반복문

다시 살펴보니까, phone_book의 배열 안 값들이 문자여서 제대로 정렬되고 있지 않았다. UTF-16 순서인 sort()로 해도 과정은 맞았지만, 원래 숫자는 위와 같은 방식이 더 정확하다고 한다.
어차피 sort로 정렬하면, 이전과 다음만 비교해도 괜찮기 때문에 이중 반복문을 안써도 괜찮았다. -> 궁금해서 클로드한테 물어봤다.
오..! 정렬 후에는 인접한 문자열만 확인해봐도 충분하다고 하니
확인받아서 뭔가 든든하다.

function solution(phone_book) {
    let answer = true;
    const arr= phone_book.sort()
    for(i=1; i<arr.length; i++){
        if(arr[i].startsWith(arr[i-1])){
            answer = false
            return answer
        }
    }
    return answer;
}

회고

생각이 많아져서 하기 싫다는 마음이 들었었는데, 막상 문제를 풀다보니 재밌다.
요즘 좀 코테 몰입에 재미를 느끼는 것 같기도..! 좋은 현상이 보인다.
오늘도 고생했다 나 자신...ㅎㅎ
내일 이 문제 복습해보자.