[프로그래머스][C++] 전화번호 목록

전화번호 목록

문제 링크

전화번호 목록

분석

전화번호 목록에서 특정 번호가 다른 번호의 접두어가 되는지 확인하는 문제입니다.

목록에서 다른 번호의 접두어가 되는 번호가 있을 경우 false를 반환하고, 반대의 경우 true를 반환하면 됩니다.

다음과 같은 전화번호가 있을 경우를 예시로 들어보겠습니다.

• 12
• 123
• 1234

번호 12가 다른 번호 123 과 1234의 접두사가 되기 때문에 false를 반환하면 됩니다.

번호의 개수를 n, 문자열 비교를 l이라고 할 때, 단순 브루트포스로 문제를 풀고자하면 $O(n^2 \tiems l)$의 시간복잡도를 가지게 됩니다.
번호 목록을 정렬하고, 인접한 번호들과만 비교하는 방법으로 접근하면 시간 복잡도를 $O(n log n) + O(n \times l)$까지 줄일 수 있습니다.

풀이

#include <string>
#include <vector>
#include <set>

using namespace std;

bool solution(vector<string> phone_book) {    
    bool answer = true;
    
    // set을 활용하여 사전순 정렬
    set<string> phoneNumberSet;
    
    for (const string& phoneNumber : phone_book)
    {
        phoneNumberSet.insert(phoneNumber);
    }
    
    set<string>::iterator it = phoneNumberSet.begin();
    // 첫 원소를 기준으로 설정
    string previous = *it;
    ++it;
    
    // 현재 원소와 이전 원소를 비교하면서 순회
    while (it != phoneNumberSet.end())
    {
        string currentPhoneNumber = *it;
        
        // 현재 문자열의 앞부분을 previous의 길이만큼 잘라 새로운 문자열 생성
        string prefix = currentPhoneNumber.substr(0, previous.size());
        
        // 접두어인지 확인
        if (prefix == previous)
        {
            answer = false;
            break;
        }
        
        // 다음 비교를 위해 갱신
        previous = currentPhoneNumber;
        ++it;
    }
    
    return answer;
}

set을 사용하여 사전순으로 정렬하여 접두억 관계가 있는 문자열들이 인접하게 위치할 수 있도록 하여 탐색을 최소화 해주었습니다.
vector 자료구조와 sort함수를 이용해주는 방법또한 가능합니다.

성능 요약

시간 복잡도는 $O(n log n) + O(n \times l)$입니다.

• set에 전화번호 목록 삽입 $(n log n)$
• set 순회 $O(n)$
• previous의 부분 문자열 생성 및 비교 $O(l)$
  • l은 문자열 길이
• $(n log n) + O(n) \times O(l)$

공간 복잡도는 $O(n \times l)$입니다.

• set의 문자열 n개 저장 $O(n \times l)$
• previous, currentPhoneNumber 등 문자열 변수들 $O(l)$
• $O(n \times l)$

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.02ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.17MB)
테스트 3 〉 통과 (0.01ms, 3.67MB)
테스트 4 〉 통과 (0.01ms, 4.22MB)
테스트 5 〉 통과 (0.01ms, 3.68MB)
테스트 6 〉 통과 (0.01ms, 3.65MB)
테스트 7 〉 통과 (0.01ms, 4.03MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 4.13MB)
테스트 12 〉 통과 (0.01ms, 4.2MB)
테스트 13 〉 통과 (0.01ms, 4.2MB)
테스트 14 〉 통과 (0.38ms, 3.89MB)
테스트 15 〉 통과 (0.51ms, 3.74MB)
테스트 16 〉 통과 (0.77ms, 4.28MB)
테스트 17 〉 통과 (0.96ms, 4.21MB)
테스트 18 〉 통과 (1.38ms, 3.99MB)
테스트 19 〉 통과 (1.28ms, 4.21MB)
테스트 20 〉 통과 (1.20ms, 4.45MB)

효율성 테스트

테스트 1 〉 통과 (4.57ms, 5.26MB)
테스트 2 〉 통과 (4.49ms, 5.23MB)
테스트 3 〉 통과 (151.89ms, 56.9MB)
테스트 4 〉 통과 (132.56ms, 49.8MB)