글 읽기 - 너무 어려워서 질문드립니다.

yslim6168 3년 전 0

제 알고리즘은 우선 지워야할 string과 지우지말아야할 string으로 Trie를 구성합니다. 단, 지우지말아야할 요소들이 포함된 Trie에는 bool doNotDel을 true로 합니다. (Trie 는 대/소문자, '.', 숫자 총 63개의 next를 가집니다.)

root->find() 시에 doNotDel이 true라면 한 글자씩 계속 current에 추가해주게 되고,

반대로 doNotDel이 false라면 고려해야할 것이 current + "*" 이거나, current + *key 가 될텐데 이는 마지막 글자냐 아니냐에 따라 달라질 것이라 생각하여 query == current로 판별하였습니다.

그후 규칙이 같다면 공통적인 command를 가질 것이라서 command모두를 set에 넣어 set의 크기만 answer로 하는 방식을 사용하였는데, 자꾸 틀려서 질문드립니다...

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>

using namespace std;

int testCase, targetCase, remainCase, answer;
string target, remain;

// 0 대문자 : 65~90
// 1 소문자 : 97~112
// 2   .    : 46
// 3  숫자  : 48~57

int checkChar(char key) {
	if (key == 46) return 2;
	if (48 <= key && key < 58) return 3;
	int base = key - 'a';
	if (0 <= base && base < 26) return 1;
	else return 0;
}

struct Trie {
	Trie* next[63];
	int charState;
	bool doNotDel;

	Trie() {
		fill(next, next + 63, nullptr);
		charState = -1;
		doNotDel = false;
	}

	~Trie() {
		for (int i = 0; i < 63; i++) if (next[i]) delete next[i];
	}

	void insert(const char* key, bool condition) {
		if (condition) doNotDel = true;
		if (*key == '\0') {
			return;
		}
		charState = checkChar(*key);
		int curr = 0;
		if (charState == 0) curr = *key - 'A';
		else if (charState == 1) curr = *key - 'a'+26;
		else if (charState == 2) curr = 52;
		else if (charState == 3) curr = *key - '0'+53;
		if (!next[curr]) next[curr] = new Trie;
		next[curr]->insert(key + 1, condition);
	}

	string find(const char* key, string query, string current) {
		if (*key == '\0') {
			if (query == current) return current;
		}
		charState = checkChar(*key);
		int curr = 0;
		if (charState == 0) curr = *key - 'A';
		else if (charState == 1) curr = *key - 'a'+26;
		else if (charState == 2) curr = 52;
		else if (charState == 3) curr = *key - '0'+53;
		if (doNotDel) {
			return next[curr]->find(key + 1, query, current + *key);
		}
		else {
			return current+ "*";
		}
	}
};


void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> testCase;
	while (testCase--) {
		Trie* root = new Trie;
		unordered_set <string> deleteSet;
		unordered_set <string> answer;
		unordered_set <string>::iterator iter;
		cin >> targetCase;
		for (int i = 0; i < targetCase; i++) {
			cin >> target;
			deleteSet.insert(target);
			root->insert(target.c_str(), false);
		}

		cin >> remainCase;
		for (int i = 0; i < remainCase; i++) {
			cin >> remain;
			root->insert(remain.c_str(), true);
		}
		
		for (iter = deleteSet.begin(); iter != deleteSet.end(); ++iter) {
			string res = root->find(iter->c_str(), *iter, "");
			//cout << res << '\n';
			answer.insert(res);
		}
		cout << answer.size() << '\n';
		delete root;
	}
}


int main() {
	input();
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

너무 어려워서 질문드립니다.

yslim6168 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말