백준 BOJ 5052 - 전화번호 목록

알고리즘 재활 2일차.

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

5052번: 전화번호 목록

랜덤으로 집어온 문제.

trie 자료구조를 통해 해결할 수 있다.

전에 아호코라식 기초문제 풀면서 분명 다뤘던거같은데

까먹어서 다시 배웠다

https://rebro.kr/86

[자료구조] 트라이(Trie) 자료구조

 

각 자릿수를 트리의 노드로 봐서

입력된 문자열을 트리로 펼쳐낸다?

나는 trie 자료구조를 보고 이런 감상을 받았다.

 

트라이 기초 구현이라서 g4 받은거 같고

처음엔 살짝 낮나 싶었는데

substr 활용해서 풀수도 있다고 한다.

 

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

bool cmp(string &s1, string &s2){
	if(s1.length() != s2.length()) return s1.length() > s2.length();
	return s1 > s2;
}

struct trie{
	trie* child[11] = {nullptr,};
	
	bool insert(string &str, int idx){
		int nxt = str[idx]-'0';
		
		if(str.length() == idx){
			for(int i=0; i<11; i++){
				if(child[i] != nullptr){
					return false;
				}
			}
			return true;
		}
		else{
			if(child[nxt] == nullptr) child[nxt] = new trie;
			return child[nxt] -> insert(str, idx+1);
		}
	}
};

int main(){	
	int t,n;
	string tmp;
	vector<string> v;
	
	cin >> t;
	while(t--){
		trie g;
		
		v.clear();
		cin >> n;
		for(int i=0; i<n; i++){
			cin >> tmp;
			v.push_back(tmp);
		}
		
		sort(v.begin(), v.end(), cmp);
		
		for(int i=0; i<n; i++){
			bool chk = g.insert(v[i], 0);
			if(chk == false){ cout << "NO\n"; goto flag; }
		}
		cout << "YES\n";
		flag:; 
	}
	return 0;
}

보통 trie면

insert와 find 두개로 함수를 분리하는데

앞부분이 같은지만 확인하면 될것 같아서

문자열의 길이가 긴 순으로 정렬한 다음에

insert함수에서 바로바로 확인해줬다.

 

 

+

@bamgoesn 님과의 대화

풀이 방법에 대한 이야기를 하면서,

모든 문자열을 사전순으로 정렬하게 되면 접두사냐 아니냐의 관계는 그 안에서 반드시 인접한 위치에 있게 되므로, 정렬 후 모든 인접한 문자열을 뒤져보면서 앞의 것이 뒤의 것의 접두사인지 체크하는 식으로 풀거나 하면 되는거같아요.

요런풀이도 있다고 해주셨는데

>>정렬<< 여기서 써먹는거 진짜 대단하다고 생각한다.

세상엔 너무 머리좋은사람이많아요

엉엉