트리 형태로 링크드리스트 형태로 '글자수'만큼(O(n))시간소요
글자 하나당 노드하나를 만들어주고 노드안에 26개(알파벳 대문자) 포인터가 쓰인다.
삼성,카카오에서 가끔 한두문제 나옴
MST,TRIE,Union-Find 3가지는 기본을 다 쌓은후 공부해보자
#include<iostream>
#include<string>
using namespace std;
struct Node {
char ch;
Node* next[26]; //대문자 26개
//int cnt 까지 추가 하여 활용가능
};
Node* head;
void init() {
head = new Node();
head->ch = '#'; //처음 노드(스타트값)
}
void insert(string str) {
Node* now = head; //head가리키고 시작
for (int i = 0; i < str.size(); i++) { //한글자씩 탐색
int index = str[i] - 'A'; //0번 index
if (now->next[index] == NULL) {
now->next[index] = new Node();
now->next[index]->ch = str[i];
}
now = now->next[index];
}
}
int main() {
init();
insert("ABC");
insert("ABS");
insert("ABCD");
return 0;
}