(프로그래머스 )카카오 코딩테스트 자동완성 문제

#include <string>
#include <vector>
#include <iostream>
#include <string.h>

using namespace std;
int total_cnt;

struct trie {
    trie * next[26];
    int count=1;

};

void dfs(trie * t) {
    if (t->count == 1) {
        total_cnt++;
        return;
    } else {
        total_cnt += t->count;
    }

    for (int i=0; i<26; i++) {
        if (t->next[i] == NULL) continue;
        dfs(t->next[i]);

    }

}


void find(const char * str, trie * t) {
    if (*str == '\0') return;
    int alpha_num = (*str)-'a';
    if (t->next[alpha_num]->count == 1) {
        total_cnt++;  
        return;
    }
    else {
       total_cnt++;

       find(str+1, t->next[alpha_num]);
    }
}



void make(const char * str, trie * t) {
    if (*str == '\0') {
        return;
    }
    int alpha_num = (*str)-'a';
    trie * node;
    trie * next_node = t->next[alpha_num];
    if (next_node == NULL) {
        node = new trie();
        t->next[alpha_num] = node;
    } else {
        node = next_node;
        (node->count)++;
    }

    make(str+1, node);
}

int solution(vector<string> words) {
    int answer = 0;
    trie * root = new trie();
    root->count = 0;
    for (auto s: words) {
        make(s.c_str(), root);

    }


    //dfs(root);

    for (auto s: words) {
        find(s.c_str(), root);
    }



    answer =  total_cnt;
    return answer;
}

일단 tri 자료구조를 생성할 때는 모든 단어를 다 검사해서 한 글자당 한 노드씩 만들었다.

이렇게 만들어 놓은 구조에서 답을 찾을 때는

1. dfs방식으로 밑으로 쭉 내려가면서 1번만 등장한 노드가 나오면 만들때 그 노드를 거쳤던 횟수를 싹 다 더해버리는 방식
2. 모든 단어를 다시 하나씩 tri 자료구조를 따라가며 검사하는 방식

2번 방식으로 하다가 시간초과 때문에 1번을 생각했던 건데 문제는 그게 아니였다.

1번과 2번은 시간 차이가 거의 안난다. find의 속도가 문제가 아니라는 뜻인 것 같다

string과 const char * 속도 차이

좌 string                         우 const char *

tri 자료구조를 이용해서 문제를 풀때는 절대 string 자료형을 사용하면 안될 것 같다. 어차피 무조건 다음 글자를 확인해야 하고, 다음 글자에 대한 접근 외에 STL string의 함수를 사용할 일도 없다.

처음에 전체 string과 1씩 늘어나는 index를 파라미터로 두고 그 때 그 때 접근해서 사용했는데 시간초과를 해결할 수 없었다. 설마해서 string.c_str()을 이용해 const char *로 바꿔보자 시간차이가 무려 20배가 났다(2000ms->100ms).

const char * 배열에 1(char이 1바이트니깐)씩 주소값을 더해 접근하든, 파라미터에 index를 추가하고 int alpha_num = *(str+index)-'a'; 이나 int alpha_num = str[index]-'a'; 처럼 매번 index만큼 직접 더해서 사용해도 시간은 거의 아무런 변화도 없다. string은 내가 당연하게 생각하던 이런식의 접근이 아닌가...? 최신 c++에서의 string은 예전과 달리 메모리도 산발적으로 있지 않고 연속적으로 있다는데 왜 이렇게 오래걸리는지 잘 모르겠다. 진짜 순수하게 str[i]로 접근하는데에만 썼는데.

심지어 cplusplus.com 피셜 constant complexity라는데 접근 자체의 문제가 아닐 수도 있겠다는 생각이 든다.

글 쓰다가 집착 도져서 테스트해봤는데 find 함수는 string이든 const char *로 하든 시간에 영향을 주지 않는다. 애초에 모든 노드를 dfs로 한번씩만 보든 모든 단어가 중복해서 보든 상관이 없었기도 했다.

make함수가 원인이였다. 문제는 생성할 때...!

같은 테스트 번호고, 심지어 메모리 사용량이 160 메가나 되어도 시간 차이가 별로 나지 않는 테스트케이스도 있다(6, 8,12,13 등).

그런데 14, 19, 21, 22번 테스트케이스같은 경우 메모리도 100메가 차이에 시간은 20배 차이가 난다.

메모리 기준은 보통 프로그램이 실행되는 도중 가장 많은 메모리를 차지했을 때라는데 string 자체가 메모리도 많이 먹고 무겁다는건 알겠는데 정확한 이유를 모르겠다 ㅜㅜ

총 글자수가 같다는 전제 하에 트라이 자료구조에서는 중복되는 글자가 많을수록 용량을 적게 먹을텐데.. 용량이 늘어났다는건 중복되는 글자가 적다는 의미일 것이다.

내가 만든 trie 자료구조는 int 1개 = 4바이트 에 포인터26개배열 = 8*26=208 바이트 총 212 바이트고

• 2 <= 단어수<= 100,000
• 2 <= 단어총길이수<= 1,000,000

212 byte * 1000000 = 212,000,000 byte = 212MB 니까

뇌피셜상 220MB가 나온건 대략 변태같이 중복이 1도 안되는 테스트인것같다.

c++ string의 구조

스트링 사이즈: 32

template <typename T>
struct basic_string {
    char* begin_;
    size_t size_;
    union {
        size_t capacity_;
        char sso_buffer[16];
    };
};

/one for short strings (small internal buffer) and one for long strings (heap-allocated external buffer)./

Small String Optimization.

 

스트링 사이즈가 무조건 32가 나오는 이유.

capacity는 small string(15글자 이하) 일 때는 15로 고정되어 있고, 그 이상의 long string에 대해서는 실제 length만큼 늘어남. 유니온을 사용한것을 보면 두 경우를 나눠 쓰는것을 알수있음

 

참고자료

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

http://www.cplusplus.com/reference/string/string/operator[]/

https://stackoverflow.com/questions/3770781/why-is-sizeofstring-32