[c++] 전화번호 목록 (프로그래머스-Trie, 정렬, 해시)

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

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

맵과함께 구현한 트라이 구조체를 만들어서 풀었슴니당
이거 풀려고 트라이 다시 공부함..
https://luen.tistory.com/108

트라이 Trie (c++ 구조체 구현)

중간에 자꾸 '.'이랑 '->' 이랑 헷갈려서 오류가 많이 났는데, ide 없이 푸려니 역시 이런 오류가 많이 나는 것 같습니다..

insert는 평범한 Trie와 같이 넣었고,
접두사는 finish와 edge 변수로 여기서 끝난 번호가 있는지, 여기가 트리의 끝인지만 구분해서
여기서 끝난 번호가 있는데 edge가 아닐경우에 false를 리턴했습니다.

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

struct Trie {
    map<char, Trie*> next;
    bool finish = false;
    bool edge = false;
    
    void insert(string& numbers, int index) {
        if ((int)numbers.size() <= index) {
            this->finish = true;
            
            if ((int)this->next.size() == 0) {
                this->edge = true;
            }
            
            return;
        }
        
        this->edge = false;
        
        map<char, Trie*>::iterator nextTrie = next.find(numbers[index]);
        if (nextTrie == next.end()) {
            Trie* newTrie = new Trie();
            next[numbers[index]] = newTrie;
            newTrie->insert(numbers, index + 1);
        }
        else {
            nextTrie->second->insert(numbers, index + 1);
        }
    }
    
    void havePrepix(bool& answer) {
        for (auto& iter: next) {
            if (this->finish && !(this->edge)) {
                answer = false; return;
            }
            else {
                iter.second->havePrepix(answer);
            }
        }
        return;
    }
};

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    Trie phoneBookTrie;
    for (int i=0; i<(int)phone_book.size(); i++) {
        phoneBookTrie.insert(phone_book[i], 0);
    }
    
    phoneBookTrie.havePrepix(answer);
    return answer;
}

 

---

번외..

근데 다른 사람의 풀이를 보니 간단하게 정렬 후 for문으로 뒤에 값들과만 비교했더라구요..
시간복잡도는 트라이가 이득일 수도있겠지만 코테는 이득이 아니게찌? ㅠ.ㅠ

그래서 효율성 테스트를 비교해봄

트라이

정렬

? 그만 알아보자.

...
메모리는 트라이가 새로 다 만드니 훨씬 높고, 시간은 왜저렇게 차이나는거지..
다른 트라이로 푼 사람의 효율성 테스트를 다시보자

왜 보냐구요? 억울해서..


트라이 (insert만)

이분은 insert 부분에서만 구현을 다해서 시간이 더 적은 느낌이긴한데

아 ㅋㅋ 잘 짠 코드는 아니었다.. 근데 어디서 못짰는지 ㅜ 이터레이터 남발해서 그런감.. ㅇㅅㅇ