[프로그래머스 2020 KAKAO BLIND RECRUITMENT] 가사 검색 -Java

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

 

import java.util.*;
class Solution {
	    public int[] solution(String[] words, String[] queries) {
	        int[] answer = new int[queries.length];
	        Trie trieFront= new Trie();
	        Trie trieBack= new Trie();
	        HashSet<Integer> wordsLenth = new HashSet<>();
	        
	        insertTire(words, trieFront, trieBack); //Trie 만들기 
	        solve(queries, answer,trieFront, trieBack ); //검색하기
	      
	        return answer;
	    }
	    
		private void solve(String[] queries, int[] answer, Trie trieFront, Trie trieBack) {
			  for(int i=0; i<queries.length; i++) {
		        	String querie=queries[i];
		        	if(querie.charAt(0)=='?') { //처음 시작이 ? 이면 word를 뒤집어 trieBack에서 검색
		        		answer[i]=trieBack.contains(new StringBuilder(querie).reverse().toString());
		        	}
		        	else { //처음은 그대로 뒷부분이 ? 이면 word를 그대로 trieFront에서 검색
		        		answer[i]=trieFront.contains(querie);
		        	}
		        }
		}
		
		private void insertTire(String[] words, Trie trieFront, Trie trieBack) {
			  for(int i=0; i<words.length; i++) {
		        	trieFront.insert(words[i]);
		        	trieBack.insert(new StringBuilder(words[i]).reverse().toString());
		        }
		}
		
		class TrieNode{
			HashMap<Character, TrieNode> childNodes = new HashMap<>(); //자식노드들
			HashMap<Integer, Integer> count = new HashMap<>(); //문자열 길이, 개수 
			
			public HashMap<Character, TrieNode> getChildNodes() {
				return childNodes;
			}
			public HashMap<Integer, Integer> getCount() {
				return count;
			}
		}
		
		class Trie{
			TrieNode rootNode;
			
			Trie(){
				this.rootNode=new TrieNode();
			}
			
			void insert(String word){
				TrieNode thisNode = this.rootNode;
				
				for(int i=0; i<word.length(); i++) {
					char ch = word.charAt(i);
					thisNode = thisNode.getChildNodes().computeIfAbsent(ch, (key)->new TrieNode());
					thisNode.getCount().computeIfPresent(word.length(), (key,value)->(value+1)); //있으면 +1
					thisNode.getCount().computeIfAbsent(word.length(), key->1); //없으면 1
                    		//각문자열에 문자열길이, 갯수 저장
				}
               		 this.rootNode.getCount().computeIfPresent(word.length(), (key,value)->(value+1)); //있으면 +1
				this.rootNode.getCount().computeIfAbsent(word.length(), key->1); //없으면 1
               		 // ???? 처럼 모든 문자가 ?로 들어오면 rootNode에 문자열길이, 갯수 저장해줘야함
			}
			
			int contains(String word) {
				TrieNode thisNode = this.rootNode;
				
				for(int i=0; i<word.length(); i++) {
					char ch = word.charAt(i);
					if(ch=='?') { //만약 물음표 들어오면 문자열길이에 해당하는거 던져주고 끝
						return  thisNode.getCount().getOrDefault(word.length(), 0);
					}
					thisNode = thisNode.getChildNodes().get(ch);
					if(thisNode==null) return 0;
				}
				return 0;
			}
		}
	}

소요시간 : 1시간 25분

 

 

트라이를 공부하고 처음 풀어봤는데 어렵네요... 아직은 익숙하지가 않은 것 같습니다.

 

만약 트라이를 모르신다면 여기서 공부하고 오셔서 다시 보셔야 합니다.

dkwjdi.tistory.com/99

트라이(Trie)

트라이를 사용하지 않고 구하는 방법은 있으나 문제상에서 제한조건인

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.

이 두 조건때문에 효율성 부분에서 시간초과가 무조건 날겁니다.

 

 

 

우선 로직을 보기 전에 fro?? 와 같이 들어온 queries는 어떻게 답을 도출할 수 있을지 생각해봅시다.

 

답은 각 노드마다 (문자 전체의 길이 : 이러한 문자가 몇개존재하는지) 를 저장해주면 됩니다.

위의 그림과 같이  [ frodo, front, frost] 가 저장되어 있다면 각 문자에서 '?'를 만났을 때

내가 속한 길이의 문자와, 그러한 길이의 문자가 몇개 있는지 저장해 놓는다면 바로 답을 return해줄 수 있습니다. 

 

그럼 로직을 살펴봅시다.

 

1. 트라이를 만든다. (trieFront, trieBack) 

자 위의 그림처럼 ?를 찾는다는것은 알게되었습니다.

그런데 queries의 입력이 ???do 처럼 들어온다면? 저 위의 방식으로는 사용할 수 없습니다.

 

이를 해결하기 위해서 trieFront, trieBack과 같이 Trie를 2개만들어 줍니다.

trieFront : 정상적으로 저장된 트라이

trieBack: 문자를 뒤집어서 저장한 트라이

queries를 입력이 ????o 일 때 trieBack에서 찾는다면 trieFront에서 fro??를 찾는것과 똑같은 방식으로 찾을 수 있습니다.

 

2. 검색한다

위에서 설명한대로 '?'를 만났을 때 입력으로 들어온 word길이와 비교해 count를 넘겨주면 됩니다.

 

 

끝~