[プログラマー]電話番号リスト(JAVA/Java)

質問リンク

に答える

hashカテゴリに分類される問題であるが,Trie(트라이)概念を適用して解釈した.
Trieとは?
探索木の一種で、文字列を迅速に探索できる資料構造である.
つまり、文字列を管理する方法の1つです.

問題例1を下図に示します.青いノードは最後の文字を表します.
119を入れて1195524421を入れると、1195524421が119の最後のノードを含んでいることがわかります!このような場合、接頭辞が存在すると考えられる.
trieインプリメンテーションは慣例に従って行われるのではなく,ノードクラスを定義することによってグラフィックを描画し,adjにサブノードを追加することによって実現される.
ルートノードから開始し、文字列の各文字を表示してサブノードを検索または新規作成します.

初期ノード(now)=ルート

nowノードのサブノードがない場合は、新しいサブノードを作成し、nowを新しいノードに置き換えます.

nowノードのサブノードで、ノード(リーフ1)が現在検索する数値を持っている場合.

文字列の末尾を確認します.

終了ノードでない場合、nowをサブノードに置き換えます(leaf 1).

エンドポイントの場合、接頭辞があるためfalseが返されます.

に現在検索する文字がない場合は、サブノードを作成し、nowを新しいノードに置き換えます.

の処理を容易にするために、文字列の各文字を表示する際に、数値で解析処理を意図的に行わなかった.(char形式を使用)

コード#コード#

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    static class Node{
        char num;		// 노드가 가지는 값
        ArrayList<Node> adj; 	// 자식 노드들의 list
        boolean is_end;		// 현재 노드가 한 문자열의 끝인지 여부

        public Node(char num) {
            this.num = num;
            this.adj = new ArrayList<>();
            this.is_end = false;
        }
    }

public static boolean solution(String[] phone_book) {
        
        // 문자열의 길이 순서대로 오름차순 정렬
        Arrays.sort(phone_book, (s1, s2)->s1.length()-s2.length());
        // Arrays.sort(phone_book, (s1, s2)->s1.compareTo(s2));  // 이렇게 해도 가능

        Node root = new Node('r'); // 루트 노드 생성

        for (int i = 0; i < phone_book.length; i++) {
            String s = phone_book[i];

            Node now = root; // 루트부터 탐색

            OuterLoop:
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);

                // 현재 노드의 자식 노드가 하나도 없으면 
                // 바로 새로운 노드를 생성하여 자식 노드로 이어주고
                // now(현재 노드)를 방금 생성한 자식 노드로 바꿔준다.
                if (now.adj.size()==0) {
                    Node new_node = new Node(c);
                    now.adj.add(new_node);
                    now = new_node;

                    if (j == s.length() - 1) { // j번째 문자가 마지막 문자라면
                        now.is_end = true; 
                    }
                    continue;
                }


                // 현재 노드(now)의 자식 노드를 하나씩 확인
                for (Node n : now.adj) {
                    if (n.num == c) {
                        if(n.is_end){ 	// 접두사가 있으면 바로 결과 리턴 (false)
                            return false;
                        }else{
                            now = n;	// 현재 노드(now)를 자식노드로 바꿔주고 다시 탐색
                            continue OuterLoop;
                        }
                    }
                }

                // 현재 숫자 값을 가진 노드가 없으면 새로 생성한다.
                Node new_node = new Node(c);
                now.adj.add(new_node);
                now = new_node;

                if (j == s.length() - 1) {
                    now.is_end = true;
                }

            }
        }

        return true;
    }
}

整理する

난이도 : LEVEL 2

🤦‍♀️ メモ

三輪車のコンセプトは毎日見ても忘れてしまいます.文字列を検索するときに有効な方法が見つかったらtrie!

他の人の解答を見ると、二重for文を使っていて、どうすれば問題を解決できるのかということでしたが、効率があまりよくないようでパスしました.

ハッシュテーブル

の使用方法について

コメントサイト

いいえ