[백준] 27652번 AB

https://www.acmicpc.net/problem/27652

27652번: AB

이문제는 집합 A의 부분 문자열과 집합 B의 부분 문자열을 합쳐서 문자열 S를 만들 수 있는 경우의 수를 구하는 문제입니다.

 

 

 

🎲 문제 풀이법

1. 문제에서 주는 쿼리에 맞게 문자열을 트라이 구조체로 저장하여 줍니다. 이때, B집합의 문자열은 접미사가 되기 때문에 문자열을 역순으로  저장해 줍니다.

2. 이때 트라이 노드에 count변수를 추가한 다음 중복하여 저장되는 부분 문자열의 갯수를 세어줍니다.

 

 

3. find 쿼리로 특정 문자열을 만들어야 할 때는 접두사A와 접미사B가 될 수 있는 경우의 수를 모두 찾아줍니다. 예를 들어 abab를 만들려면 a+bcd, ab+cd, abc+d로 총 세가지가 나옵니다.

 

4. 문자열S가 만들어질 수있는 경우를 모두 찾았다면 각각의 접두사와 접미사가 만들어 질 수 있는 경우의 수도 구해줍니다.  위의 경우를 보면 접두사 a가 만들어질 경우의 수는 1가지, 접미사 bcd가 만들어 질 경우는 0가지이기 때문에 둘을 곱해서 총 0가지의 a+bcd 형태의 문자열이 만들어집니다. 그다음번인 접두사ab가 만들어질 경우의 수는 1가지이고 접미사 cd가 만들어질 경우의 수도 1가지이기 때문에 둘을 곱해주면 ab+cd형태의 문자열이 만들어지는 경우의 수는 총 1가지 입니다.

 

5. 위의 방식으로 각각의 쿼이 add, delete, find함수에 따라 작동하도록 구현하여 주면 됩니다.

 

#include <stdio.h>
#include <string>
#include <string.h>
#include <fstream>
#include <iostream>
#include <list>
#include <vector>
#include <queue>
#include <math.h>
#include <unordered_map>
#include <algorithm> 

using namespace std;



int N, M;

int table[110][110];
bool visited[110][110];
unordered_map<string, int> hashMap_A, hashMap_B;

struct Trie
{
	int countA, countB;
	Trie* nodes[26];

	Trie()
	{
		countA = 0;
		countB = 0;
		for (int i = 0; i < 26; i++) nodes[i] = nullptr;
	}


	void Add(const char* ch)
	{
		if (*ch == '\0') return;
	
		if (nodes[*ch - 'a'] == nullptr) nodes[*ch - 'a'] = new Trie();
		nodes[*ch - 'a']->countA++;
		nodes[*ch - 'a']->Add(ch + 1);
	}
	void Add_Reverse(const char* ch, int size)
	{
		if (size <= 0) return;
	
		if (nodes[*ch - 'a'] == nullptr) nodes[*ch - 'a'] = new Trie();
		nodes[*ch - 'a']->countB++;
		nodes[*ch - 'a']->Add_Reverse(ch - 1, size - 1);
	}

	void Delete(const char* ch)
	{
		if (*ch == '\0') return;
	
		if (nodes[*ch - 'a'] == nullptr) nodes[*ch - 'a'] = new Trie();
		nodes[*ch - 'a']->countA--;
		nodes[*ch - 'a']->Delete(ch + 1);
	}

	void Delete_Reverse(const char* ch, int size)
	{
		if (size <= 0) return;

		if (nodes[*ch - 'a'] == nullptr) nodes[*ch - 'a'] = new Trie();
		nodes[*ch - 'a']->countB--;
		nodes[*ch - 'a']->Delete_Reverse(ch - 1, size - 1);
	}
	
	int Find(const char* ch, int size)
	{
		if (size <= 0) return countA;
		if (nodes[*ch - 'a'] == nullptr) return 0;

		return nodes[*ch - 'a']->Find(ch + 1, size - 1);
	}
	
	int Find_Reverse(const char* ch, int size)
	{
		if (size <= 0) return countB;
		if (nodes[*ch - 'a'] == nullptr) return 0;

		return nodes[*ch - 'a']->Find_Reverse(ch - 1, size - 1);
	}
};
Trie* root;

int Find_A(string& str)
{
	if (hashMap_A.find(str) == hashMap_A.end())
		hashMap_A[str] = root->Find(str.c_str(), str.size());

	return hashMap_A[str];
}

int Find_B(string& str)
{
	if (hashMap_B.find(str) == hashMap_B.end())
		hashMap_B[str] = root->Find_Reverse(str.c_str() + str.size() - 1, str.size());

	return hashMap_B[str];
}

int main()
{
	root = new Trie();

	cin >> N;
	cin.ignore();

	string str;
	char command[100];
	char content[1010];

	int found_A[1010];
	int found_B[1010];
	int content_size;
	char set;
    
	for (int i = 0; i < N; i++)
	{
		scanf("%s\n", command);

		if (command[0] == 'a') {
			scanf("%c", &set);
			scanf("%s", content);
			content_size = strlen(content);

			if (set == 'A')
				root->Add(content);
			else if (set == 'B') {
				root->Add_Reverse(content + content_size - 1, content_size);
			}

		}
		else if (command[0] == 'd')
		{
			scanf("%c", &set);
			scanf("%s", content);
			content_size = strlen(content);

			if (set == 'A')
				root->Delete(content);
			else if (set == 'B') {
				root->Delete_Reverse(content + content_size - 1, content_size);
			}
		}
		else if (command[0] == 'f')
		{
			scanf("%s", content);
			content_size = strlen(content);

			int total = 0;

			Trie* tempA = root;
			Trie* tempB = root;

			int i;
			for (i = 0; i < content_size; i++) {
				found_A[i] = tempA->countA;
				if (tempA->nodes[content[i] - 'a'] == nullptr) break;
					tempA = tempA->nodes[content[i] - 'a'];
			}
			for (i = i + 1; i < content_size; i++)
				found_A[i] = 0;
            
			for (i = content_size - 1; i >= 0; i--) {
				found_B[i] = tempB->countB;
				if (tempB->nodes[content[i] - 'a'] == nullptr) break;
				tempB = tempB->nodes[content[i] - 'a'];
			}
			for (i = i - 1; i >= 0; i--)
				found_B[i] = 0;

			for (int i = 1; i < content_size; i++)
			{
				total += found_A[i] * found_B[i - 1];

			}
			printf("%d\n", total);
		}
	}

	return 0;
}

 

 

 

🍳 어려웠던 점

    1. find쿼리를 처리할 때 각각의 접두사와 접미사를 전부 따로 구했는데 이럴경우 시간초과가 나옵니다. 각 접두사와 접미사의 경우의 수는 a, ab, abc, abcd 이런식으로 연결되어있기 때문에 순차적으로 트라이 구조체를 내려가면서 전부 구해주시면 시간 초과를 해결할 수 있습니다.