[프로그래머스 / Level4] 가사 검색 (Java)

문제 보기

사용한 것

• 문자열을 문자 하나씩 노드로 트리에 저장한다.

풀이 방법

• 문자 하나를 노드로 트리에 저장하여 풀었지만 시간 효율성을 통과하지 못했다.
• Trie를 사용하여 다시 한번 풀어봐야겠다.

코드

class Solution {

    Node head = new Node();

    public int[] solution(String[] words, String[] queries) {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            Node node = head;
            for (int j = 0; j < word.length(); j++) {
                String letter = word.substring(j, j + 1);

                if (!node.nextNodes.containsKey(letter)) {
                    node.nextNodes.put(letter, new Node());
                }

                if (j == word.length() - 1) {
                    node.nextNodes.get(letter).setWord(true);
                }

                node = node.nextNodes.get(letter);
            }
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {

            answer[i] = bfs(queries[i]);
        }

        return answer;
    }

    public int bfs(String query) {
        Queue<Node> q = new LinkedList<>();
        q.offer(head);
        int num = 0;
        for (int i = 0; i < query.length(); i++) {
            String letter = query.substring(i, i + 1);
            List<Node> list = new ArrayList<>();
            while (!q.isEmpty()) {
                list.add(q.poll());
            }

            for (Node node : list) {
                if (letter.equals("?")) {
                    for (Node nextNode : node.nextNodes.values()) {
                        q.offer(nextNode);
                    }
                } else {
                    if (node.nextNodes.containsKey(letter)) {
                        q.offer(node.nextNodes.get(letter));
                    }
                }
            }
        }

        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node.isWord) {
                num++;
            }
        }

        return num;
    }
}

class Node {

    public boolean isWord = false;
    public Map<String, Node> nextNodes;

    public Node() {
        this.nextNodes = new HashMap<>();
    }

    public void setWord(boolean word) {
        isWord = word;
    }
}