[JAVA] 가사검색 (kakao 2020 프로그래머스)

 

 

<풀이>

 

trie 자료구조로 문제를 푼다.

 

1) 문자열 저장

만약 "fla","fly","ka" 문자열들을 가진다면 트라이 자료구조는 아래처럼 될 것이다.

 

 

2) 길이정보 저장하기

 

만약 쿼리를 "fro??"로 준다면 fro 로 시작하고 5글자인 모든 문자열의 수를 알아야 한다. 

 

본인은 각 노드마다 문자열들의 수를 저장하는 해시맵을 각각의 노드마다 추가했다.

 

1)에서의 정보를 바탕으로 자료구조를 수정하면 다음과 같다.

 

 

 

(x:y) 의 의미는 x길이의 문자열의 수는 y 다.

즉, (3:2) 는 길이가 3인 문자열의 수가 2개 있다는 뜻이다.

 

문제)

쿼리가 "fl?"로 왔다면

 

 

답) 파란박스에서 lenHashMap.get(3) 

 

 

"?" 로 시작하는 문자열은 문자열을 거꾸로 만들어서 똑같이 구현하면 된다.

 

<전체코드와 결과>

 

import java.util.*;
class Solution {
        public int[] solution(String[] words, String[] queries) {
            int[] answer = new int[queries.length];
            Trie frontTrie = new Trie();
            Trie backTrie = new Trie();
            for(String s : words){
                frontTrie.addWord(s);
                backTrie.addWord(new StringBuffer(s).reverse().toString());
            }
            int i=0;
            for(String s : queries){
                if(s.charAt(0)=='?'){
                    answer[i++]=backTrie.search(new StringBuffer(s).reverse().toString());
                }else answer[i++]=frontTrie.search(s);
            }
            return answer;
        }

        static class Node{
            char data;
            HashMap<Character,Node> child = new HashMap<>();
            HashMap<Integer,Integer> lenHashMap = new HashMap<>();

            public Node(char data){
                this.data = data;
            }

        }

        static class Trie{
            Node head;

            public Trie(){
                head = new Node('#');
            }

            public void addWord(String s){
                Node cur = head;
                for(char c : s.toCharArray()){
                    if(cur.lenHashMap.containsKey(s.length())){
                        int lenCnt = cur.lenHashMap.get(s.length());
                        cur.lenHashMap.replace(s.length(),lenCnt+1);
                    }else{
                        cur.lenHashMap.put(s.length(),1);
                    }
                    if(!(cur.child.containsKey(c))){
                        cur.child.put(c,new Node(c));
                    }
                    cur = cur.child.get(c);

                }
            }


            public int search(String s){
                Node cur = head;
                for(char c : s.toCharArray()){
                    if(c=='?') break;
                    else if(cur.child.containsKey(c)){
                        cur = cur.child.get(c);
                    }
                    else{
                        return 0;
                    }
                }
                if(cur.lenHashMap.containsKey(s.length()))
                return cur.lenHashMap.get(s.length());
                else return 0;
            }

        }

    }