[c++] 프로그래머스 42577 :: "전화번호 목록" 풀이 및 코드

문제

전화번호 목록 문제 바로 가기

코딩테스트 연습 - 전화번호 목록

 

풀이

보자마자 트라이(Trie)가 생각났다. 문자열 길이도 20 이하이니 최대 높이가 20인 트리를 만들면 될 것 같다. 하지만 연결리스트 구현이 너무 귀찮기도 하고, 입력의 범위가 10^6이라 O(nlgn) 이하로 한 번에 해결할 수 있는 쉬운 방법이 있지 않을까 생각했다. 정렬되어 있는 phone_book을 한 번에 훑으면 등장했던 문자열을 포함하고 있는 지를 확인하면 되는데, 일반적으로 등장했던 모든 문자열을 다시 순회하는 방식은 "정렬비용 (O(nlgn)) + 순회비용 (O(n^2))" 이라 시간복잡도가 상당하다. 따라서, 한 번에 해결하기 위해서는 공간 복잡도를 증가시키고 시간 복잡도를 감소 시킬 방향을 찾아야 하는데 이 때 생각한 것이 map 자료 구조이다.

 

{ key : 전화번호, value : 아무 값 } 으로 되어있는 map을 생성 한 후에, 각 전화번호를 앞에서부터 한 글자씩 늘려가며 map에 해당 문자열이 있는 지 보면 된다. 전화번호는 20 이하이므로 "정렬비용 (O(nlgn)) + 순회 비용 (O(n*20))" 인 총 O(nlgn)의 시간복잡도로 해결 할 수 있다.

 

 

코드

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

using namespace std;

bool solution(vector<string> phone_book) {
    map<string, bool> phoneMap;
    
    sort(phone_book.begin(), phone_book.end()); // 전화번호 정렬
    
    for(int i=0; i<phone_book.size(); i++){
        string phoneNumber = phone_book[i];
        for(int j=1; j<=phoneNumber.size(); j++){
            string str = phoneNumber.substr(0, j); // 한 글자씩 늘려가며
            if(phoneMap[str]) { // 이미 나온 적 있는 번호인지 확인
                return false;
            }
        }
        phoneMap[phoneNumber] = true; // map에 전화번호 등록
    }
    
    return true;
}

 

 

결과