프로그래머스 LV.2 전화번호 목록

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

프로그래머스

 
해당 문제는 전화번호가 접두어인가? 를 판별하면 된다.
접두어이면 FASLE, 아니면 TRUE를 반환한다.
 
제한 사항

• 폰북의 길이가 1 ~ 1000000이다.
• 각 전화번호의 길이는 1 ~ 20 사이이다.
• 같은 전화번호는 중복해서 들어가 있지 않다

 
해당 문제의 접근법은 3가지가 있다.
 

1. 반복문을 활용
   - 시간이 너무 오래 걸린다. 폰북의 길이가 너무 길다.
   - 이중 루프를 돌게된다.(양방향 비교) 
2. 정렬과 반복문을 활용
   - 이중 루프를 돌지 않게 된다 (단방향 비교)
   - 시간이 너무 오래 걸린다.
3. 해시를 활용
   - 해시맵을 이용해서 key와 value를 통해 테이블 제작 (Hashing)
   - 순차적으로 해당 접두어가 맵에 있는지 확인한다. (Hash 찾기)
   - 접두어를 찾아야하기 때문에,
     기존 전화번호와 같은 수를 hashmap에 존재하는지 확인하면 안된. (에외처리)
   - 해시맵의 탐색 속도는 O(1)의 속도를 가지기 때문에 효율적인 탐색이 가능하다.

 
 
1번 방법은 너무 오래걸리므로 패스하겠다.
 

2. 정렬과 반복문을 활용한 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    
    // 폰북 배열 정렬
    sort(phone_book.begin(), phone_book.end());

    // 1중 포문을 돌며 앞 번호가 윗 번호의 접두어인지 확인하기
    for (int i = 0; i < phone_book.size() - 1; i++) {
        if (phone_book[i + 1].find(phone_book[i]) == 0)
            return false;
    }

    // 여기까지 왔다면 접두어가 없다는 것
    return true;
}

 
해당 코드를 프로그래머스에 돌리면 다음과 같은
정확성과 효율성을 보여준다.

 

3. 해시를 활용한 코드

bool solution(vector<string> phone_book) {
    
    // HashMap 제작
    unordered_map <string, int> map;

    for (int i = 0; i < phone_book.size(); i++) {
        map[phone_book[i]] = 1;
    }

    // 모든 전화번호의 substring(접두어가) HashMap에 있는지 확인한다.
    for (int i = 0; i < phone_book.size(); i++) {
        for (int j = 1; j < phone_book[i].size(); j++) {
            // 순차적으로 글자 수 만큼 담는다.
            string phone_num = phone_book[i].substr(0, j);
            // 맵에 해당 폰넘버가 있는가?
            if (map[phone_num])
                return false;
        }
    }

    // 여기까지 왔다면 접두어가 없다는 것
    return true;
}