[백준 27652번 문제] AB

문제설명

집합 두개가 있고 3가지 커맨드가 있음

add,

delete,

find,

add, delete는 더하고 지우기 가 끝

find는 문자열을 둘로 나눠서 앞의 부분은 A 뒷부분은 B에서 찾을 수 있는 경우의 수의 총합을 찾아서 출력하는 함수다.

입력

첫째 줄에 쿼리의 개수 Q

n줄동안

add A aba delete A a find abab

출력

find 구문마다 나올 수 있는 경우의 수의 총합을 출력

과정

처음에는 이렇게 생각했다 

일단 find쿼리에서 일어나는 일은 O(문자열길이) 안에 끝내야한다고 생각한다. 애초에 집합으로 저장해야한다고 하기도 했고 해시가 바로떠오른다. 저장되는 쿼리 양도 해봤자 1000이다.

유일하게 걱정되는건 subStr이 O(글자수)라고 알고있는데 1000 글자라면

어찌됐던 1000 * 1000 번 연산이 일어난다.

물론 쿼리 개수 자체가 1000이기 때문에 개수 처리가 가능하다면 모든 1000개를 다 둘러봐야할 필요는 없긴하다.

만약 이게 별로라면 문자열 탐색을 좀 더 쉽게할 수 있는 방법이 있어야한다. 근데 트라이로 쓰면 어떻게 해결이 될 것 같긴하다.

말그대로 unordered_map을 가정해서 모든 경우의수 다보면 되지않나?? 싶었던 건데 알고보니 문제 조건이 접두어 접미어였다. Trie를 쓰면 find할 때 0번째문자부터 최대 1000번째 문자까지 새로운 문자열을 계속 만들지 않고 문제를 풀 수 있다

Trie 
{
	private:
		int num : 호출값 add될시 1씩 더해지고 delete 될시 1씩 작아짐 
		Trie* next[26] : 다음 Trie들을 담아두고있는 배열
	public:
		void addWord : input문장의 0번 인덱스에 해당하는 자식 배열에게 1번부터 마지막까지의 문자열을 제공
										자기의 값 ++  
		void removeWord : 들어온 완전한 문장의 0번 인덱스에 해당하는 자식 배열에게 1번부터 마지막까지 문자열 제공
												자기자신 num --, 자기 자식이 비어있는지 확인한뒤 비었다면 delete해준다
		void fillUpTable : B라면뒤집고 A라면 그대로인 트라이에 대해서 n번째 까지의 인덱스가 얼마나 차있는가를 적는다. -1이 아니라면
		주어진 문자열의 다음 인덱스가 있는질 확인하고 없다면 리턴하며 있다면
			
		boolean isEmpty : 비어있는지 확인한다. num을 통해
}

 

간략하게 이야기하면 트라이의 각 노드는 자신의 문자뿐 아니라 자신이 호출된 횟수를 저장할 수 있다. addword에서 substr을 해나가면서 [단어] => [문자의 배열] 구조를 만들기 때문에 abcd, abde 두개의 단어중 a와 b는 같은 노드를 지나가게 되고 나중에 find에서 모든 문자를 다 보지않아도 되게 만들어준다.

 

remove에 대해서도 마찬가지로 호출될때마다 한칸씩 줄이는 방향으로 하면 될 것이라고 생각했다. 그리고 모든 나 또는 내 next배열의 놈이 delete 호출뒤에 num이 0일경우 즉 해당 접두어가 없을경우는 delete로 메모리를 지우면된다.

 

find의 경우에는 a의 접두어와 b의 접미어의 최대길이 999만큼 미리 몇가지의 경우가 있는지 확인해주면 된다.

주어지는 word를 가지고 계속 트라이를 탐색, 값을 배열에 추가한뒤

vectorA와 vectorB를 만들어 둘이 만들어 질 수 있는 최대 1000개의 순서쌍 (1, 999), (2, 998) ... 을 확인해주면 find가 수억번의 연산에서 수천번으로 줄어들게된다. 이런 개념으로 다음과 같이 문제를 풀었다 

 

알고리즘 개요도

알고리즘 개요도

알고리즘

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
 
class Trie
{
public:

    int num;
    char val;
    Trie* next[26];

    Trie(char val) : val(val), num(0) {
        for (int idx = 0; idx < 26; idx++)
        {
            next[idx] = nullptr;
        }
    }; 
    void addWord(string word)
    {
        if (word.empty() == false)
        {
            int nextidx = word[0] - 'a';
            if (next[nextidx] == nullptr)
            {
                next[nextidx] = new Trie(word[0]);
            }
            next[nextidx]->addWord(word.substr(1));
        }
        num++;
    }
    void deleteWord(string word)
    {   
        
        if (word.empty() == false)
        {
            int nextidx = word[0] - 'a';
            next[nextidx]->deleteWord(word.substr(1));
            if (next[nextidx]->empty())
            {
                delete next[nextidx];
                next[nextidx] = nullptr;
            }
        }
        num--;
    }
    Trie* fillUpTable(char c, int index, vector<int> &table)
    {   
        if (c == '#')
        {
            table[index] = num;
            return nullptr;
        }
        if (c && c != ' ')
        {   
            if (index != -1)
            { 
                table[index] = num;
            }
            if (next[c - 'a'] != nullptr)
            {
                return next[c - 'a'];
            }
            else
            {
                return nullptr;
            }
        }

    }

    bool empty()
    {
        return num == 0;
    }

};


int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    
    int C;
    cin >> C;
    Trie* headA = new Trie('&');
    Trie* headB = new Trie('&');    

    for (int i = 0; i < C; i++)
    {
        string s;
        cin >> s;
       

        if (s == "add")
        {
            char whichOne;
            cin >> whichOne;
            if (whichOne == 'A')
            {
                string word;
                cin >> word;
                headA->addWord(word);
            } 
            else 
            {
                string word;
                cin >> word;
                reverse(word.begin(), word.end());
                headB->addWord(word);
            }
        }
        else if (s == "delete")
        {
            char whichOne;
            cin >> whichOne;
            string word;
            cin >> word;
            
            if (whichOne == 'A')
            {   
                headA->deleteWord(word);
            }
            else 
            {
                reverse(word.begin(), word.end());
                headB->deleteWord(word);
            }
        }
        else
        {
            string word;
            cin >> word;
            int wordLength = word.length();

            vector<int> vectorA (wordLength, 0);
            vector<int> vectorB (wordLength, 0);
            Trie* fillA = headA;
            Trie* fillB = headB;
            for (int j = -1; j < wordLength; j++)
            {
                char ca = j != wordLength - 1 ? word[j + 1] : '#';
                char cb = j != wordLength - 1 ? word[wordLength - j - 2] : '#';
                if (fillA != nullptr) 
                {
                    Trie* newA = fillA->fillUpTable(ca, j, vectorA);
                    fillA = newA;
                }
                if (fillB != nullptr)
                {
                    Trie* newB = fillB->fillUpTable(cb, j, vectorB);
                    fillB = newB;
                }
            }

            int ans = 0;
            for (int j = 0; j < word.length() - 1; j++)
            {
                ans += vectorA[j] * vectorB[word.length() - j - 2];
            }
            cout << ans << '\n';
        }
    }
}

이런 트라이나 클래스를 이용하는 문제는 객체 참조를 편하게 하기위해서 메소드형식을 선호하게되는데 트라이는 더미 헤드를 만들어놓는 방식으로 하다보니 항상 양끝의 에러케이스를 많이 생각해줘야한다.

또한 이번 문제에서 delete를 적극적으로 활용했는데 포인터와 관련해 두가지 오류가 있었다.

1. delete 이후 nullptr로 지정하지 않을시 생기는 오류
2. Trie* new[26] 배열을 초기화하지 않을시 생겼던 오류

이게 말로만 듣던 dangling 에러인가 싶었다. 이참에 포인터에 대한 공부를 더 해놓아야겠다.

결과