프로그래머스 - 전화번호 목록

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

프로그래머스

 

아래와 같은 흐름으로 접근을 시작했다.

1. 긴 전화번호는 짧은 번호의 접두사가 될 수 없으므로, 번호의 길이 순으로 정렬한다.

2. 이중 for문을 돌며 i번째 전화번호와 그 이후 index의 전화번호들을 비교한다.

3. startsWith 메서드를 통해 i번 째 전화번호로 시작하는 번호가 있을 경우 false, 이외에는 true를 반환한다.

 

function solution(phone_book) {
    var answer = true;
    phone_book.sort((pre, acc) => pre.length - acc.length)
    
    loop1: for (let i=0; i < phone_book.length; i++) {
       const targetNum = phone_book[i]
       for (let j=i+1; j < phone_book.length; j++){
           const compareNum = phone_book[j]
           if (compareNum.startsWith(targetNum)) {
               answer = false
               break loop1
           } 
       }
    }
    
    return answer;
}

구현한 코드!

효율성에서 실패가 나온다.

이리저리 고민을 해보다...

1. 최초 sort시 전화번호의 길이로 정렬할 필요가 없다!

→ 길이가 짧고 길고 와 관계없이... 문자의 순서(유니코드)대로 정렬한 뒤 앞에서부터 비교하면 되기 때문.

2. 이중 for문을 끝까지 돌 필요가 없다!

→ 문자 순서대로 정렬한 경우, i번째 전화번호가 i+1번째 전화번호의 접두사가 아니라면 i+n번째 전화번호 역시 접두사일 수가 없기 때문.

 

function solution(phone_book) {
    var answer = true;
    phone_book.sort()
    
    loop1: for (let i=0; i < phone_book.length; i++) {
       const targetNum = phone_book[i]
       for (let j=i+1; j < phone_book.length; j++){
           const compareNum = phone_book[j]
           if (compareNum.startsWith(targetNum)) {
               answer = false
               break loop1
           } else {
               break
           }
       }
    }
    
    return answer;
}

위 논리를 반영한 코드!

그리고 위 코드는 i번째와 i+1번째를 비교하는 것과 동일하므로...

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

위와 같이 작성해 줄 수도 있겠다.

---

맨 처음 '긴 전화번호는 짧은 번호의 접두사가 될 수 없다'는 생각이 들었는데,

한 번 이 생각이 들고 나니 sort를 길이순대로 + 끝까지 비교해야 한다 는 논리에서 빠져나오기가 힘들었다.

→ 구현하고자 하는 논리를 명확히 하되, 잘 풀리지 않을 경우 해당 논리의 오류부터 점검해야 함을 느꼈다.