백준 BOJ 5670 - 휴대폰 자판

재활 3일차

시뻘건 문제를 잡아보았다.

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

5670번: 휴대폰 자판

트라이 자료구조형을 활용해야 하는데

단순히 포함여부만을 물어보는 문제가 아니라서 티어가 좀 높게 책정된 것 같다.

 

사용자의 입력이 필요한 경우가

1. 트라이 자료구조 내부의 트리에서 자식노드가 두개 이상 있을때

2. 자식노드가 한개 있는데 해당 노드가 문자열의 끝인 경우

 

2번 경우가 좀 비 직관적일수도 있을것 같은데 음

원하는 문자열의 끝까지 온 경우 / 다른 문자열이라서 더 입력해줘야하는경우

이 구분을 위해서 2번에 대한 처리를 해주어야 한다.

 

그리고 메모리 초과를 받는것 같으니 트라이 자료구조에 대한 소멸자를 만들어주자.

 

#include <bits/stdc++.h>
using namespace std;

struct trie{
	trie *child[26] = {nullptr,};
	bool isEnd = false;
	
	~trie(){
		for(int i=0; i<26; i++) if(child[i] != nullptr) delete(child[i]);
	}
	
	void insert(string &in, int ptr){
		if(in.length() == ptr) isEnd = true;
		if(in.length() > ptr){
			int nxt = in[ptr] - 'a';
			if(child[nxt] == nullptr) child[nxt] = new trie;
			child[nxt]->insert(in, ptr+1);
		}
		return;
	}
	
	int find(string &in, int ptr){
		int nxt = in[ptr] - 'a';
		if(ptr == 0) return child[nxt]->find(in,ptr+1)+1;
		
		int ans = 0;
		if(in.length() > ptr){
			int cnt = 0;
			
			for(int i=0; i<26; i++) if(child[i] != nullptr) cnt++;
			
			if(cnt>1) ans++;
			if(isEnd && cnt==1) ans++;
			return child[nxt]->find(in, ptr+1) + ans;
		}
		return 0;
	}
};

int main(){
	int n;
	while(cin >> n){
		vector<string> v(n);
		trie t;
		int sum_v = 0;
		
		for(int i=0; i<n; i++){
			cin >> v[i];
			t.insert(v[i], 0);
		}
		
		for(int i=0; i<n; i++){
			sum_v += t.find(v[i],0);
			//printf("[%d]", t.find(v[i],0));
		}
		printf("%.2f\n", (double)sum_v/n);
	}
	
	return 0;
}

제법 오래걸렸다만 일단 AC.