2022.07.27. (Trie) 풀이

다룬 태그

• Trie (ABCDEF)

A. [14725] 개미굴 (Gold III)

트라이를 구축하는 문제입니다.

차이점이라면, 문자열에서 하나의 글자를 들고 오는 대신

문자열의 배열에서 하나의 문자열을 꺼내서 쓰는 정도의 차이가 있습니다.

 

(사실 이 문제는 트라이 없이도 풀 수 있습니다. 그래서 Gold III이라는 낮은 난이도를 받은 거고요.)

struct Node{ map<string, int> nxt; };
vector<Node> trie;
void psh(int ni, vector<string>& v, int vi){ int vl = v.size();
	if (vi == vl){ return; }
	if (trie[ni].nxt.count(v[vi]) == 0){
		trie[ni].nxt[ v[vi] ] = trie.size();
		trie.push_back( Node() );
	}
	return psh(trie[ni].nxt[ v[vi] ], v, vi+1);
}
inline void psh(vector<string>& v){ return psh(0, v, 0); }

void dfs(int ni, int dep = 0){
	for (pair<string, int> p : trie[ni].nxt){
		for (int i = 0; i < dep; i++){ cout << "--"; }
		cout << p.fr << endl;
		dfs(p.sc, dep+1);
	}
}

void Main(){
	trie.push_back( Node() );
	int n; cin >> n; while (n--){
		vector<string> v;
		int m; cin >> m; while (m--){
			string s; cin >> s; v.push_back(s);
		}
		psh(v);
	}
	dfs(0);
}

B. [5670] 휴대폰 자판 (Platinum IV)

트라이를 구축한 뒤, 각 단어를 적기 위한 시뮬레이션을 돌려봅시다.

이는 루트 정점에서 출발해서,

어떤 정점에서 갈랫길이 여러개라면 버튼을 직접 누르는 방식으로 이동해주고,

갈랫길이 1개밖에 없으면 버튼을 누르지 않고 이동해주는 방식으로 돌려주면 됩니다.

 

평균을 출력하라고 했지만, 이는 그냥 총합 / N이기 때문에 시뮬레이션을 돌리면서 버튼 누르는 횟수의 총합을 구해주면 됩니다.

루트 정점에서 출발할 때는 갈림길이 없어도 버튼을 눌러줘야 함에 주의하세요!

struct Nod{ int cnt=0; bool chk=0; int nxc=0; int nxt[30] = {}; };
vector<Nod> tri;

string arr[100020];

void psh(int ni, const string& s, int idx){ int sl = s.size();
	tri[ni].cnt += 1;
	if (idx == sl){ tri[ni].chk = 1; return; }
	int& nxt = tri[ni].nxt[ s[idx]-'a' ];
	if (nxt == 0){ tri[ni].nxc += 1;
		nxt = tri.size(); tri.push_back( Nod() );
	}
	return psh(tri[ni].nxt[ s[idx]-'a' ], s, idx+1);
}

ll ans = 0;
void qry(int ni, const string& s, int idx){ int sl = s.size();
	if (idx == sl){ return; }
	if (tri[ni].chk || tri[ni].nxc != 1 || ni == 0){ ans += 1; }
	return qry(tri[ni].nxt[ s[idx]-'a' ], s, idx+1);
}

void Main(){
	int n; while (cin >> n){
		tri.push_back( Nod() );
		for (int i = 1; i <= n; i++){ cin >> arr[i]; psh(0, arr[i], 0); }
		ans = 0; for (int i = 1; i <= n; i++){ qry(0, arr[i], 0); }
		cout << (ld)ans/n << endl;
		tri.clear();
	}
}

C. [13505] 두 수 XOR (Platinum III)

입력받은 수들을 모두 트라이에 넣어준 뒤,

각 수에 대해서 xor max를 구해주면 됩니다.

struct Nod{ int nxt[2] = {}; };
vector<Nod> tri;

int arr[100020];

void psh(int ni, const int& val, int idx){
	if (idx < 0){ return; }
	int nxi = val>>idx & 1;
	int& nxt = tri[ni].nxt[nxi];
	if (nxt == 0){
		nxt = tri.size(); tri.push_back( Nod() );
	}
	return psh(tri[ni].nxt[nxi], val, idx-1);
}

ll res = 0;
void qry(int ni, const int& val, int idx){
	if (idx < 0){ return; }
	int nxi = val>>idx & 1;
	if (tri[ni].nxt[1^nxi]){ res |= 1<<idx; return qry(tri[ni].nxt[1^nxi], val, idx-1); }
	else{ return qry(tri[ni].nxt[nxi], val, idx-1); }
}

void Main(){
	int n; cin >> n;
	tri.push_back( Nod() );
	for (int i = 1; i <= n; i++){ cin >> arr[i]; psh(0, arr[i], 30); }
	ll ans = 0;
	for (int i = 1; i <= n; i++){ res = 0; qry(0, arr[i], 30); ans = max(ans, res); }
	cout << ans;
}

D. [16903] 수열과 쿼리 20 (Platinum III)

1번 쿼리와 3번 쿼리는 수업에서 다뤄봤습니다.

 

그럼 남은 건 2번 쿼리, 제거 쿼리인데,

제거를 위해 실제로 정점을 할당 해제하고 하는 등의 방식은 번거로우니,

그냥 정점에 저장된 '수의 개수'에서 1을 빼주면 됩니다.

 

대신, 탐색을 할 때도 그냥 '정점이 있는가'가 아니라

'정점이 있으며, 수의 개수가 1개 이상인가'로 탐색해야겠죠.

const int N = 32;

struct Node{
	int cnt;
	int nxt[2];
	Node(){ cnt = 0; nxt[0] = nxt[1] = -1; }
};

vector<Node> tri;

void push(int node, int bit, int idx){
	//cout << "PUSH " << node << ' ' << bitset<4>(bit) << ' ' << idx << endl;
	tri[node].cnt += 1;
	if (idx < 0){ return; }
	int val = !!(bit & 1<<idx);
	int nxt = tri[node].nxt[val];
	if (nxt == -1){
		nxt = tri.size();
		tri.push_back( Node() );
	}
	tri[node].nxt[val] = nxt;
	//cout << "CALL " << nxt << ' ' << bit << ' ' << idx-1 << endl;
	push(nxt, bit, idx-1);
}

void pop(int node, int bit, int idx){
	tri[node].cnt -= 1;
	if (idx < 0){ return; }
	int val = !!(bit & 1<<idx);
	pop(tri[node].nxt[val], bit, idx-1);
}

int ans;

void qry(int node, int bit, int idx){
	if (idx < 0){ return; }
	ans <<= 1;
	int val = !(bit & 1<<idx);
	int nxt1 = tri[node].nxt[val];
	int nxt2 = tri[node].nxt[val^1];
	//cout << "OPT " << nxt1 << ' ' << tri[nxt1].cnt << endl;
	if (nxt1 != -1 && tri[nxt1].cnt != 0){
		//cout << "NXT1 " << val << endl;
		ans |= val;
		qry(nxt1, bit, idx-1);
	}
	else{
		//cout << "NXT2 " << (val^1) << endl;
		ans |= val^1;
		qry(nxt2, bit, idx-1);
	}
}

void Main(){
	tri.push_back( Node() );
	push(0, 0, N-1);
	int q;
	cin >> q;
	while (q--){
		int m;
		cin >> m;
		if (m == 1){
			int a;
			cin >> a;
			push(0, a, N-1);
		}
		if (m == 2){
			int a;
			cin >> a;
			pop(0, a, N-1);
		}
		if (m == 3){
			int a;
			cin >> a;
			ans = 0;
			qry(0, a, N-1);
			ans ^= a;
			cout << ans << endl;
		}
	}
}

E. [20919] XOR 자료구조 (Platinum III)

add(v)는, 평소에 하던 Trie에 수 넣기입니다.

 

remove_min은, 현재 정점에서 0의 방향으로 가는 게 1의 방향으로 가는 것보다 항상 더 작은 수가 되니 (사전순을 생각해보세요) 가능하면 0의 방향으로 탐색하는 방식으로 수를 찾은 뒤, 삭제해주면 됩니다.

remove_max도 0과 1 바꿔서 비슷하게 처리할 수 있습니다.

 

find_max는 이미 수업에서 처리했습니다.

find_min도 0과 1 바꿔서 비슷하게 처리해주면 됩니다.

const int M = 24;
struct Nod{ int cnt = 0; int nxt[2] = {}; };
vector<Nod> tri;
void psh(int ni, int val, int bit){
	if (bit < 0){ tri[ni].cnt = 1; return; }
	int nxi = val>>bit & 1;
	int& nxt = tri[ni].nxt[nxi];
	if (nxt == 0){ nxt = tri.size(); tri.push_back(Nod()); }
	psh(tri[ni].nxt[nxi], val, bit-1);
	tri[ni].cnt = 0;
	for (int nxi : {0, 1}){
		if (tri[ni].nxt[nxi] == 0){ continue; }
		tri[ni].cnt += tri[ tri[ni].nxt[nxi] ].cnt;
	}
}
inline int qry1(int ni, int val, int bit){
	if (bit < 0){ return 0; }
	int nxi = val>>bit & 1;
	int nxt = tri[ni].nxt[nxi];
	if (nxt != 0 && tri[nxt].cnt > 0){
		return qry1(tri[ni].nxt[nxi], val, bit-1);
	}
	else{
		return qry1(tri[ni].nxt[nxi^1], val, bit-1) | 1<<bit;
	}
}
inline int qry2(int ni, int val, int bit){
	if (bit < 0){ return 0; }
	int nxi = val>>bit & 1;
	int nxt = tri[ni].nxt[nxi^1];
	if (nxt != 0 && tri[nxt].cnt > 0){
		return qry2(tri[ni].nxt[nxi^1], val, bit-1) | 1<<bit;
	}
	else{
		return qry2(tri[ni].nxt[nxi], val, bit-1);
	}
}
inline int qry4(int ni, int bit){
	tri[ni].cnt -= 1;
	if (bit < 0){ return 0; }
	int nxt = tri[ni].nxt[0];
	if (nxt != 0 && tri[nxt].cnt > 0){ return qry4(tri[ni].nxt[0], bit-1); }
	else{ return qry4(tri[ni].nxt[1], bit-1) | 1<<bit; }
}
inline int qry5(int ni, int bit){
	tri[ni].cnt -= 1;
	if (bit < 0){ return 0; }
	int nxt = tri[ni].nxt[1];
	if (nxt != 0 && tri[nxt].cnt > 0){ return qry5(tri[ni].nxt[1], bit-1) | 1<<bit; }
	else{ return qry5(tri[ni].nxt[0], bit-1); }
}

void Main(){
	int t; cin >> t;
	while (t--){
		int n, q; cin >> n >> q;
		tri.push_back(Nod());
		while (n--){
			int x; cin >> x; psh(0, x, M);
		}
		while (q--){
			int typ; cin >> typ;
			if (typ == 1){ int x; cin >> x; cout << qry1(0, x, M) << endl; }
			if (typ == 2){ int x; cin >> x; cout << qry2(0, x, M) << endl; }
			if (typ == 3){ int x; cin >> x; psh(0, x, M); cout << tri[0].cnt << endl; }
			if (typ == 4){ cout << qry4(0, M) << endl; }
			if (typ == 5){ cout << qry5(0, M) << endl; }
		}
		tri.clear();
	}
}

F. [16902] mex (Platinum III)

트라이에 수를 넣으면서, 각 정점에 들어간 수의 개수를 같이 세봅시다.

그럼, xor을 한 뒤, mex를 구할 때

xor을 해서 0이 되는 쪽에 0부터 X-1까지 다 있지 않다면, 그 없는 수가 mex가 되기 때문에 0이 되는 쪽으로 탐색을 이어야 합니다.

그렇지 않다면, 1이 되는 쪽으로 탐색을 이어나가면 됩니다.

struct Node{ int cnt = 0; int nxt[2] = {0, 0}; };
const int B = 20; vector<Node> trie;
void psh(int ni, int val, int b){
	trie[ni].cnt += 1;
	if (b < 0){ return; }
	int nxp = val>>b & 1;
	if (trie[ni].nxt[nxp] == 0){
		trie[ni].nxt[nxp] = trie.size();
		trie.push_back( Node() );
	}
	psh(trie[ni].nxt[nxp], val, b-1);
}
inline void psh(int val){ return psh(0, val, B); }

int num = 0;
int qry(int ni, int b){
	if (b < 0){ return 0; }
	int nxp = num>>b & 1;
	if (trie[ni].nxt[nxp] == 0){ return 0; }
	else if (trie[ trie[ni].nxt[nxp] ].cnt == 1<<b){
		return qry(trie[ni].nxt[nxp^1], b-1) | 1<<b;
	}
	else{ return qry(trie[ni].nxt[nxp], b-1); }
}
inline int qry(){ return qry(0, B); }

set<int> s;
void Main(){
	int n, q; cin >> n >> q;
	trie.push_back( Node() );
	while (n--){
		int x; cin >> x; s.insert(x);
	}
	for (int x : s){ psh(x); }
	while (q--){
		int x; cin >> x; num ^= x;
		cout << qry() << endl;
	}
}