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

📝 문제 설명

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

프로그래머스

목표: 주어진 전화번호부에서 어떤 번호가 다른 번호의 접두어인 경우가 존재하는지를 확인해야 한다.

핵심조건

• 전화번호부에는 같은 번호가 중복으로 들어있지 않다.
• 전화번호의 길이는 1 이상 20 이하
• 접두어의 길이는 전화번호의 길이 조건만 충족한다면 제한이 없다 (내 해석)

---

🔍 풀이 과정 (나만의 풀이 전략)

주어진 테스트 케이스에 의하면

["12","123","1235","567","88"] 이렇게 주어지면 “12”를 접두어인 번호는 “123”, “1235”이 될거고

“123”이 접두어인 경우도 “1235” 이렇게 된다. 접두어는 하나라는 조건이 없다.

단 문제의 목표는 전화번호부가 주어졌을 때 접두어인 경우가 하나라도 있다면 false를 리턴해주는 것이므로, 모든 접두어 케이스를 다 찾을 필요는 없다.

첫 번째 방법

배열을 순회하면서 접두어인 케이스를 찾는 방법은 어떨까?

이 경우에는 배열을 이중으로 순회해야한다. 즉 이중 for문 형태가 된다.

위 케이스처럼 곧바로 “12”를 접두어를 갖는 번호가 바로 다음 번호인 “123” 인 경우도 있겠지만, 최악의 경우 배열을 모두 순회해야할 수도 있다. 이 경우에는 시간 복잡도는 O(N^2)이 될 것이기 때문에 적절한 방법은 아닐 것이므로, 이 방법은 패스

두 번째 방법

해시 테이블 자료구조를 활용하는 방법으로 접근해보자.

Map 객체를 활용하여 접두어 - 번호(key-value) 형태로 구성해본다.

Map(5) {
  '12' => [],
  '123' => [],
  '1235' => [],
  '567' => [],
  '88' => []
}

위와 같은 형태로 Map 객체를 생성하고

phone_book 배열을 다시 순회하면서 phone_book의 요소가 Map의 key에 포함되는지를 정규표현식을 활용하여 알아내고 동일한 경우는 제외하고 key에 포함되는 경우라면 map.set을 통해 배열에 삽입하도록 한다?

 

이 방법 역시 동일하게 배열과 map 객체를 함께 순회하면서 정규 표현식으로 포함된다면 set하는 방식이기 때문에 똑같이 O(N^2)의 시간복잡도 문제에 직면한다…

세 번째 방법

동일하게 Map 객체를 생성하고난 후

주어진 전화번호부를 순회하면서 전화번호의 앞 숫자부터 하나하나 확인하면서 Map 객체에 해당 번호가 포함되어있는지를 체크하는 방식으로 확인한다.

이 때 검사하는 번호 자기 자신도 맵에 들어있으므로 이 경우는 제외한다.

for (const phone of phone_book) {
        let arr = ""
        for (const num of phone) {
            arr += num
            if (arr !== phone && newMap.has(arr)) {
                return false;
            }
        }
    }

전화번호 문자열을 내부에서 순회하면서 앞의 숫자부터 확인하기 위해 arr 이라는 변수를 선언하여 앞 번호 숫자부터 추가하면서 arr이 전화번호 phone과 같은지(자기 자신을 비교하는걸 방지) 그리고 해시 맵이 arr 숫자를 포함하는지 체크한다.

 

예를들어

["119", "97674223", "1195524421"] 의 경우에는

“119”의 경우는 arr은 먼저 “1” 이는 해시맵에 없으므로 패스, 다음은 “11” 이도 없으므로 패스 “119” 이는 해시맵에 존재하나 “119”와 “119”를 비교하는건 동일한 번호를 비교하는 것이므로 패스

다음으로 “1195524421”는 동일한 방법으로 진행하다가 “119”의 경우 해시 맵에 존재하고 arr “119”는 phone “1195524421”과 같지 않으므로 즉, “1195524421”는 접두어로 “119”를 가지는 경우라고 판명된다.

이를 확인하면서 false 를 리턴하면서 solution 함수는 종료된다.

+ 또 다른 방법

해시 맵을 활용하지 않는 방법으로 phone_book 배열을 sort()를 통해 정렬한다.

정렬하게 되면 전화번호의 숫자가 사전식으로 정렬되므로

["119", "97674223", "1195524421"] → ["119", "1195524421", "97674223"] 이렇게 정렬된다.

 

이렇게 되면 배열을 순회하면서 바로 인접한 옆의 요소와 비교하면서 접두어로 시작하는지를 확인하면 된다.

결국 문제의 목표는 접두어로 시작되는 전화번호의 경우가 있는가? 여부 이기 때문이다.

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;
}

💻 코드 (Code)

---

function solution(phone_book) {
    const newMap = new Map();
    
    for (const phone of phone_book) {
        newMap.set(phone, true);
    }
    
    for (const phone of phone_book) {
        let arr = ""
        for (const num of phone) {
            arr += num
            if (arr !== phone && newMap.has(arr)) {
                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;
}

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습

• String.prototype.startsWith(searchString, position)
  • 어떤 문자열의 문자로 시작하는지 확인하여 결과를 true 혹은 false로 반환한다.
  • position은 발견될 것으로 예상되는 위치의 인덱스 값을 넣어준다.
• String.prototype.substring(indexStart, indexEnd)
  • string의 시작 인덱스부터 종료 인덱스 전까지 문자열 부분을 반환한다.
  • indexEnd는 옵셔널 생략된 경우 문자열 끝까지 추출한다. indexStart와 같을 경우 빈 문자열 반환
• Array.prototype.sort([compareFunction])
  • compareFunction 콜백함수는 옵셔널하며, 이를 제공해주지 않으면 배열 요소를 문자열로 변환하고 사전식으로 오름차순 정렬합니다.

💬 마무리하며

---

주어진 배열을 그대로 가지고 접두어를 가지는 경우를 찾는 방법과 문제의 의도에 맞게 해시 맵을 활용하여 해결하는 두 가지 해결 방법이 존재했습니다. 물론 이 답을 결국 스스로 찾지 못하고 정답을 보고 말았다는 점이 너무나도 아쉬운 부분으로 남습니다…🥲 두 번째 방법론의 경우에는 해시 맵을 활용한다고 했으나 해시 맵의 장점인 요소 조회에 드는 시간 복잡도가 O(1) 이라는 부분을 전혀 활용하지 못한 방법이었던 게 문제였던 것 같습니다.

 

또한, 해결 방법이 이중 for문 형태를 취하기는 하지만 전화번호부의 길이 N은 1 이상 1,000,000 이하지만 전화번호 자체 L은 1 이상 20 이하 이기 때문에 배열 자체를 이중으로 순회하는 방법은 O(N^2) 이지만, 배열 순회 내에서 전화 번호를 순회하여 포함되는지 확인은 O(N * L) 이기 때문에 후자가 훨씬 성능 면에서 좋다는 점이 키 포인트인 것 같습니다. 무조건 이중 for문이라고 피하는게 아니라 주어진 조건을 잘 확인해서 시간 복잡도를 계산하는 자세를 갖춰야 되겠다고 느꼈습니다.