먼저 후기부터 적으면 되게 고생한 문제...
트라이를 처음 접한 것과 달리 트라이를 구현하는 건 어렵지 않았다.
하지만 map을 사용할 때 초기화를 제대로 안해줘서 문제가 생겼는데 문제점을 못찾아 고생했다.
맞왜틀
직관적으로 접근하면 당연하지만 문자열 비교의 횟수가 어마무시하기 때문에 불가능하다.
trie라는 자료구조를 활용해 접근해 연산 횟수를 획기적으로 줄일 수 있다.
문제 풀이는 trie 구현과 주어진 팀 이름의 앞 뒤에서 양쪽으로 탐색해서 연산 횟수를 줄이는게 핵심이다.
우선 색과 이름을 각각의 trie에 저장을 하고 색은 앞에서부터 이름은 뒤에서부터 검색을 한다.
이 때 검색된 색의 길이들과 검색된 이름의 길이들의 조합의 합이 전체 팀 이름의 길이와 같으면 가능한 경우로 판단하면 된다.
이것 저것 작성하는 기술 블로그