[C++/해시] 전화번호 목록

문제 출처

프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42577

 

문제 설명

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

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

이전 문제 풀이

https://think-deeply.tistory.com/5?category=934880 

[해시/C++] 전화번호 목록

---

코드 & 문제 풀이

1. O(n²) 풀이

전화번호 배열의 모든 값을 나머지 값에 비교해 접두어인지 확인

정확한 방법이긴 하나 효율성 테스트 실패

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    string base;
    
    for (int i=0; i<phone_book.size(); i++) {
        base = phone_book[i];
        for(int j=i+1; j<phone_book.size(); j++) {
            if(base == phone_book[j].substr(0, base.size())){
                return false;
            }
        }
    }
    
    return answer;
}

 

2. 해시맵 사용

정렬한 뒤 해시맵의 key 값과 전화번호 문자열을 비교.

해시맵을 쓰는데 sort 함수가 그렇게 중요한 역할을 하진 않았다. (리스트 앞 쪽에 접두어 포함된 문자열이 있으면 더 빨라지는 정도)

시간복잡도는 input 벡터 정렬 O(n log n), 문자열 별 해시맵 검색 O(n²)... 사실 위의 경우에서 크게 개선된 점 없는듯

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    map<string, int> m;
    string base;
        
    for (int i=0; i<phone_book.size(); i++) {
        for(int j=1; j<phone_book[i].size(); j++){
            if(m.find(phone_book[i].substr(0, j)) != m.end())
                return false;            
        }
        m[phone_book[i]] = 0;
    }
    
    return answer;
}

효율성 테스트

테스트 1 〉	통과 (3.50ms, 4.42MB)
테스트 2 〉	통과 (3.67ms, 4.54MB)
테스트 3 〉	통과 (562.78ms, 56.8MB)
테스트 4 〉	통과 (645.46ms, 44.4MB)

 

3. 정렬 사용

그러다 정렬이 숫자 크기가 아니라 사전식(ex. "1", "123", "3", "3566", "7", ...)으로 정렬된다는 것을 깨닫고 수정.

해시맵 사용 없이 문자열 비교하면 시간복잡도 O(n log n) 안에 풀 수 있다.

정렬 O(n log n) + 문자열 비교 O(n)*20 => O(n log n) 

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

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
        
    for (int i=0; i<phone_book.size()-1; i++) {
        if (phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size())){
            answer = false;
            break;
        }
    }
    
    return answer;
}

효율성 테스트

테스트 1 〉	통과 (3.72ms, 4.52MB)
테스트 2 〉	통과 (3.72ms, 4.27MB)
테스트 3 〉	통과 (81.25ms, 35.7MB)
테스트 4 〉	통과 (77.54ms, 31.5MB)

 

설명

string.substr(start, end);

문자열 자르는 함수로, 시작(start) 인덱스부터 마지막(end) 인덱스 - 1 까지의 문자열 반환

 

map.find(key) != map.end()

특정 key가 맵에 존재하는지 찾는 함수로, 존재하지 않으면 map.end() 반환