01-25 16:17
벤치마킹
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 가족소고기외식
- 양양솔비치조식
- 검색완료
- 주차넉넉
- 사진문자추출하기
- 종이캐리어
- 당근마켓중고차
- 고마워다음
- 영통칠프로칠백식당
- 사진에서 글자추출
- 파이썬
- 싱가폴중학교수학문제
- 양양솔비치아침
- 에어아시아
- 커피쏟음
- 중학교입학수학문제
- 커피
- 양양솔비치세프스키친
- 아이혼자다녀옴
- 편도수술
- 결항
- 사진문자추출
- 양양솔비치 뷔페
- 홍시스무디
- 영통역소고기
- 영통외식
- 오트눈썰매장
- 푸르지오포레피스
- 결항전문
- DFS
Archives
- Today
- Total
너와나의 관심사
Tire 자료구조에서 메모리 줄여서 구현 본문
Trie 메모리 때문에 Node * ptr 대신에 integer 형태로 코드 변환
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | #include <iostream> #include <stdio.h> #include <iomanip> using namespace std; #define MAX_N 100005 #define ALPHABET_NUM 26 int nodeCnt = 0; struct Node { bool finish; int child[ALPHABET_NUM]; int NumNextWord; } trieNode[1000001]; char arr[MAX_N][81]; int myAlloc() { nodeCnt; for (int i = 0; i < ALPHABET_NUM; i++) { trieNode[nodeCnt].child[i] = -1; } trieNode[nodeCnt].finish = false; trieNode[nodeCnt].NumNextWord = 0; return nodeCnt++; } void add(int root, char *str) { int cur = root; int i; for (i = 0; str[i]; i++) { int Idx = str[i] - 'a'; if (trieNode[cur].child[Idx] != -1) { cur = trieNode[cur].child[Idx]; } else { int nxt = myAlloc(); //next 의 값이 있기 때문에// trieNode[cur].child[Idx] = nxt; trieNode[cur].NumNextWord++; cur = nxt; } } trieNode[cur].finish = true; } int find(int root, char* str) { int cur = root; int ret = 0; for (int i = 0; str[i]; i++) { int Idx = str[i] - 'a'; //0은 무조건 // if (i == 0) ret++; else if (trieNode[cur].NumNextWord > 1) ret++; else if (trieNode[cur].finish) ret++; cur = trieNode[cur].child[Idx]; } return ret; } int N, M; int main() { //ios_base::sync_with_stdio(false); //cin.tie(NULL); // freopen("input.txt", "r", stdin); setbuf(stdout, NULL); int inpNum = 0; while (cin >> N) { //count 초기화 // nodeCnt = 0; int root = myAlloc(); for (int i = 1; i <= N; i++) { cin >> arr[i]; add(root, arr[i]); } int typeNum = 0; for (int i = 1; i <= N; i++) { typeNum += find(root, arr[i]); } printf("%.2lf\n", (double)typeNum / N); //cout << fixed << setprecision(2) << (double)typeNum / (double)N << '\n'; } return 0; } |
Comments