[코테연습] 2416. Sum of Prefix Scores of Strings

- 트라이 ( Trie ) / 문자열 문제

 

https://leetcode.com/problems/sum-of-prefix-scores-of-strings/description/?envType=daily-question&envId=2024-09-25

 

- 문제분석

1. String[] words 의 문자열 배열이 있다.

2. 문자열 배열의 원소가 ( words[i] ) 의 접두사를 확인한다.

2-1. "abc" 가 있으면, "a", "ab", "abc" 가 원소 ( words[i] ) 1개의 접두사가 된다.

3. 전체 배열 ( words ) 의 문자열을 대상으로 접두사 여부를 확인한다.

4. 접두사가 동일한 경우 원소의 점수를 카운팅한다.

4-1. "abc", "ab" 가 있는 경우, words[i] 의 0 번째 원소의 점수는 다음과 같다.

4-2. "a", "ab", "abc" 만큼의 3가지 점수와, words[i] 의 1번째 원소의 "ab" 가 0번째 원소의 접두사에 해당하므로 총 4점이다.

5. 각 원소의 점수를 int[] 배열로 리턴하라.

 

- 문제풀이

1. Trie 알고리즘을 이용하여  String[] words 문자열을 카운팅한다.

 

> 참고 : https://codingnojam.tistory.com/40

[Algorithm] Trie를 Java로 구현해보자!

 

2. Trie 알고리즘을 사용할 때, count 변수를 Node 에서 초기화하여 누적하여 카운팅한다.

3. String[] words 를 다시 반복하여, answer[i] 를 초기화 하여 리턴한다.

 

class Solution {
    public int[] sumPrefixScores(String[] words) {
        Trie trie = new Trie();
        int n = words.length;
        for(int i = 0; i < n; i++) {
            trie.insert(words[i]);
        }
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = trie.search(words[i]);
        }

        return answer;
    }

    public class Trie {

        Node root = new Node();

        void insert(String str){
            Node node = this.root;
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                node = node.childNode.computeIfAbsent(c, key->new Node());
                node.count++;
            }
        }

        int search(String str){
            Node node = this.root;
            int count = 0;
            for(int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                node = node.childNode.get(c);
                count += node.count;
            }
            return count;
        }

        public String toString(){
            return ""+this.root;
        }
    }

    public class Node {
        Map<Character, Node> childNode = new HashMap<>();
        int count;
        public Node(){}
        public Node(int count){
            this.count = count;
        }

        public String toString(){
            return "[ child : "+this.childNode+", count : "+this.count+"  ]";
        }
    }
}