백준 5052 전화번호 목록 쉬운 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/5052

문제 접근

• TRIE 기본 문제
• 개념 참조 : https://dev-jango.tistory.com/14

시간복잡도 계산

• 모든 문자열에 대해 순회 N
  • 문자열에 대해 한글자 한글자 순회 : M
  • O(NM) : 50 * 1e4 : 5e5

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include <iostream> #include <queue> #include <vector>   using namespace std;   // 각 노드의 인접 리스트 vector<int> adj[32010]; // 각 노드에 들어오는 간선 개수 int indeg[32010]; int main() {     ios::sync_with_stdio(0);     cin.tie(0);          int N,M; cin >> N >> M;     for(int i=0; i<M; i++) {         int a,b; cin >> a >> b;         // 인접한 간선 추가         adj[a].push_back(b);         // 들어오는 간선의 개수 증가         indeg[b]++;              }          queue<int> q;     for(int i=1; i<=N; i++) {         if(indeg[i]==0) q.push(i);     }          vector<int> rs;     while(!q.empty()) {         int eq = q.front(); q.pop();         rs.push_back(eq);                  for(int x : adj[eq]) {             // 들어오는 간선의 개수 감소             indeg[x]--;             // 만약 들어오는 간선의 개수가 0일때 큐에 추가             if(indeg[x] == 0) q.push(x);         }     }          for(int ers : rs) cout << ers << ' ';          return 0; }   Colored by Color Scripter

cs

문제유형

• TRIE