패스트캠퍼스 챌린지 19일차

야호~ 오늘은 기분이 좋은 게..! 드디어 원하고 원하고 원했던 백준 2990번 단어 검색 문제를 풀어냈기 때문이다..! 그것도 c++로..! c++로 이뤄낸 최초의 성과라고 볼 수 있겠다..! 메모리도 깔끔하게 사용했고, 시간도 준수했다. 다만 이 풀이가 정해인 걸로 보이긴 하는데, 빠른 풀이를 보니까 다른 풀이 방식인 것 같다. 코드를 잘 이해하지는 못하겠는데, 시간이 될 때 공부해봐야겠다. 

 

아래는 해당 코드이다. 

#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

const int AL = 27;
int n;

struct Node
{
    vector<pair<char, Node *>> child;
    int visit;
    int end;
    Node() : visit(0), end(n - 1) {}
    ~Node()
    {
        for (auto &p : child)
        {
            delete p.second;
        }
    }

    void insert(string &s, int i, int &idx)
    {
        if (s.size() == i)
        {
            child.push_back(make_pair(0, new Node()));
            child.back().second->visit += 1;
            end = idx;
            return;
        }
        for (auto &p : child)
        {
            if (p.first == s[i])
            {
                p.second->visit += 1;
                p.second->insert(s, i + 1, idx);
                return;
            }
        }
        child.push_back(make_pair(s[i], new Node()));
        child.back().second->visit += 1;
        child.back().second->insert(s, i + 1, idx);
    }

    int find(string &s, int i)
    {
        if (s.size() == i)
            return end;
        for (auto &p : child)
        {
            if (s[i] == p.first)
                return p.second->find(s, i + 1);
        }
        return n - 1;
    }

    int value(string &s, int i)
    {
        int result = 0;
        for (auto &p : child)
        {
            result += p.second->visit;
        }
        if (s.size() == i)
            return result;
        for (auto &p : child)
        {
            if (p.first == s[i])
            {
                result += p.second->value(s, i + 1);
                break;
            }
        }
        return result;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    string word[n];
    Node *root;
    root = new Node();
    for (int i = 0; i < n; i++)
    {
        cin >> word[i];
        root->insert(word[i], 0, i);
    }
    int q;
    string search;
    cin >> q;
    int idx;
    vector<tuple<int, string, int>> query;
    Node *nroot = new Node();
    for (int i = 0; i < q; i++)
    {
        cin >> search;
        idx = root->find(search, 0);
        query.push_back(make_tuple(idx, search, i));
    }
    sort(query.begin(), query.end());
    int li = -1, ni = 0;
    int result[q]{};
    for (auto &p : query)
    {
        ni = get<0>(p);
        for (int i = li + 1; i <= ni; i++)
        {
            nroot->insert(word[i], 0, i);
        }
        result[get<2>(p)] = nroot->value(get<1>(p), 0);
        li = ni;
    }
    for (int r : result)
        cout << r << '\n';

    delete root, nroot;

} // namespace std;

트라이를 구성하는 방법과 코드는 종만북을 많이 참고했다. 갠 적으로 트라이 클래스와 노드 클래스를 구분해서 사용하면 코드가 깔끔하지만, 노드만으로 트라이를 구현하는 이 방식도 불필요한 메모리를 줄일 수 있어서 좋은 것 같다. 다만 아직 c++의 메모리 관리에 대해 잘 이해하고 있는 게 아닌지라.. 동적 할당을 해준 c++코드에서 마지막에 delete를 해주긴 했는데 안 해주면 어떻게 되는지는 잘 모르겠다. 어차피 코드 실행이 끝나면 해제돼서 괜찮으려나..? 싶다.

 

문제풀이 과정에서 아직 강의에서는 배우지 않은 pair, tuple, sort에 대해 알게되었다. 파이썬에 비해 사용 방식이 번거롭고 답답하긴 하지만, 그래도 있는 게 어디인가..! sort로 정렬이 되는 것도 좋았다.

 

이제 오늘 배운 강의 내용이다..! 오늘 배운 것은 this 포인터와 const에 대한 내용이었다. this포인터는 사실상 java의 this나 python의 self와 같은 모양이었다. 다만 이 this가 포인터이기 때문에 발생하는 문제가 있는데 이를 해결하기 위해 const에 대해 배우는 듯했다.

 

const 포인터에 포인터를 넣는 것은 가능하지만 일반 포인터에 const포인터를 넣으면 에러가 난다. 그도 그럴 것이 const 포인터는 변경되면 안되기 때문에 일반 포인터에 대입되는 경우 암시적으로 변경될 수도 있기 때문이다. 그런데 메서드에 this를 넘겨줄 때 사실 상 해당 객체를 일반 포인터로 넘겨주기 때문에 객체가 const 포인터로 선언되어있는 경우 일반 포인터에 const 포인터를 넘겨주는 것과 같게 된다. 따라서 에러가 발생하고 문제가 생길 수 있다.

 

이때 메서드 옆에 const를 붙여주게 되면 this를 const 포인터로 받게 되고 에러가 생기지 않게 된다. 따라서 변경이 없는 메서드의 경우 const를 반드시 붙여주어야 한다고 한다.

 

 

const에 대해 배우는 모습

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

패스트캠퍼스 : https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

 

#패스트캠퍼스 #패캠챌린지 #직장인인강 #직장인자기계발 #패스트캠퍼스후기 #C++실력완성올인원패키지