[Java]Baekjun 5052号[電話番号リスト]Java


白俊5052号です.
https://www.acmicpc.net/problem/5052

質問する


電話番号のリストを表示します.この場合、リストが一致しているかどうかを判断するプログラムを作成します.
電話番号リストを一致させるには、1つの番号が別の番号の接頭辞であってはならない.
例えば、電話番号リストが次のような場合を考えてみましょう.
  • 緊急電話:911
  • 上根:97625999
  • 善英:91125426
  • このような状況では、善英に電話することはできない.ソンヨンが電話を取って、番号の3番目の位置を押した瞬間、緊急電話がかかってくるからだ.したがって、このリストは一致しないリストです.

    入力


    第1行は、試験例の個数tを与える.(1≦t≦50)各試験例の第1行には、電話番号の数nが与えられる.(1≦n≦10000)以下のn行には、リストに含まれる電話番号が与えられる.電話番号の長さは最大10桁で、リストの2つの電話番号が同じではない場合.

    しゅつりょく


    各テストケースについて,一致するリストであればYES,そうでなければNOを出力する.

    入力例

    2
    3
    911
    97625999
    91125426
    5
    113
    12340
    123440
    12345
    98346

    サンプル出力

    NO
    YES

    考える


    これはプログラマーの「電話番号リスト」と同じ問題です.
    各テストケースに接頭辞があることを確認するだけです.

    アクション


    まず、Hashmapを使用して解凍する方法は、電話帳を作成し、mapを生成することである.
    また、map番号と同じ配列number_list[]も生成される.
    	if(map.containsKey(number_list[i].substring(0, j))) {
    			return false;
    	}
    number_list[]からmapにキー値が含まれているか否かを判断する.
    接頭辞があるかどうかを確認します.
    Arrays.sortを行うのは,短い文字列と前の数字を比較するためである.
    なぜなら、前から長い数字を入力すると、後の短い数字は接頭辞比較ができないからです.
    配列で解く方法は
    	if(number_list[i + 1].startsWith(number_list[i])) {
    
    			return false;
    	}
    number_list前の値をstartsWith関数と比較します.
    boolean値を返します.
    Hash mapの使用

    ゲートアレイの使用

    なんといっても、別に並ぶので、
    Hashmapはメモリと速度の部分から失われる可能性があります.
    でも両方使えたら、これからも役に立つと思います.

    TMI


    昔の電話を使いますか.

    コード#コード#


    HashMapの使用

    import java.util.*;
    import java.io.*;
    
    public class Main {
    	public static void main(String[] args) throws Exception {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringBuilder sb = new StringBuilder();
    
    		int T = Integer.parseInt(br.readLine());
    		while(T --> 0) {
    			int N = Integer.parseInt(br.readLine());
    			HashMap<String, Integer> map = new HashMap<>();
    			String number_list[] = new String[N];
    
    			for(int i=0; i<N; i++) {
    				String str = br.readLine();
    				map.put(str, 1);
    				number_list[i] = str;
    			}
    
    			Arrays.sort(number_list);
    			boolean bol = solution(N, number_list, map);
    
    			if(bol == false) {
    				sb.append("NO\n");
    			}
    			else {
    				sb.append("YES\n");
    			}
    
    		}
    
    		System.out.println(sb);
    	} // End of main
    
    	static boolean solution(int length, String[] number_list, HashMap<String, Integer> map) {
    
    		for(int i=0; i<length; i++) {
    			for(int j=1; j<number_list[i].length(); j++) {
    				if(map.containsKey(number_list[i].substring(0, j))) {
    					return false;
    				}
    			}
    		}
    
    		return true;
    	} // End of solution
    } // End of class

    ゲートアレイの使用

    import java.io.*;
    import java.util.Arrays;
    
    public class Main {
    	public static void main(String[] args) throws Exception {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringBuilder sb = new StringBuilder();
    
    		int T = Integer.parseInt(br.readLine());
    		while(T --> 0) {
    			int N = Integer.parseInt(br.readLine());
    			String number_list[] = new String[N];
    
    			for(int i=0; i<N; i++) {
    				number_list[i] = br.readLine();
    			}
    
    			Arrays.sort(number_list);
    	
    			if(solution(N, number_list)) {
    				sb.append("YES\n");
    			}
    			else {
    				sb.append("NO\n");
    			}
    
    		}
    
    		System.out.println(sb);
    	} // End of main
    
    	static boolean solution(int N, String[] number_list) {
    
    		for(int i=0; i<N-1; i++) {
    			if(number_list[i + 1].startsWith(number_list[i])) {
    
    				return false;
    			}
    		}
    
    		return true;
    
    	} // End of solution
    } // End of class