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

C++에서 map을 사용한 해시로 쉽게 풀 수 있다.

 

나는 보자마자 트라이를 쓰는 문제 같았다.

해시를 떠올리지 못했다.

 

해시로 푸는 방법은 아래 블로그 참고

[Programmers] 전화번호 목록

 

 

트라이의 특징은 문자열의 종료 위치를 표시해준다는 점이다.

따라서 주어진 배열을 먼저 길이 순으로 오름차순 정렬하고, 길이가 같은 경우에는 문자열의 값에 따라 오름차순 정렬한다.

이렇게 먼저 정렬해주면 뒤에 나오는 문자열이 그보다 앞에 나오는 문자열의 접두사인 경우를 배제할 수 있다.

그렇게 트라이로 풀 수 있는 조건이 성립하게 된다.

 

 

트라이에 문자를 하나씩 넣으면서 트라이를 구성해나간다.

1-1-9 라는 문자열이 들어있고 9에 종료 표시가 되어있다.

그리고 119212 라는 문자열이 들어온다고 가정하자.

1-1-9 까지 동일하게 트라이로 탐색하게 된다.

이때 9에 도달했을 때, 문자열이 끝난적이 있기 때문에 자신의 접두사를 발견한 것이다.

따라서 중복 여부를 체크해주고 종료한다.

 

전체 코드

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

using namespace std;

#define NUM 10

struct trie{
    bool is_end = false;
    trie *child[NUM] = {NULL, };
};


bool check = false;
void Insert(string &str, trie *root){
    if(root->is_end){
        check = true;
        return;
    }
    if(str.size() == 0){
        root->is_end = true;
        return;
    }
    else{
        int n = str[0] - '0';
        if(root->child[n] == NULL) root->child[n] = new trie;
        str.erase(str.begin());
        Insert(str, root->child[n]);
    }
}

bool Compare(string a, string b){
    if(a.length() == b.length()) return a < b;
    else return a.length() < b.length();
}

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end(), Compare);
    trie *root;
    root = new trie;

    for(int i = 0; i < phone_book.size(); i++){
        Insert(phone_book[i], root);
        if(check) return false;
    }

    return true;
}