[白俊]14425号:文字列セット

📌 質問する
N個の文字列からなる集合Sが与えられる.
セットSに入力としてM個の文字列が何個含まれているかを計算するプログラムを作成してください.
入力
第1行は、文字列の個数NおよびM(1≦N≦10000、1≦M≦10000)を与える.
以下のN行は、集合Sに含まれる文字列を与える.
次のM行は、チェックする文字列を示します.
入力文字列は小文字のみで構成され、長さは500を超えません.集合Sには同じ文字列が複数回与えられていない.
しゅつりょく
第1行出力M文字列のうち、集合Sに含まれるものは合計何個であるか.
入力例1

5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
codeplus
codeminus
startlink
starlink
sundaycoding
codingsh
codinghs
sondaycoding
startrink
icerink

サンプル出力1

4

📌 に答える

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    static String[] NM;
    static ArrayList<String> list = new ArrayList<>();

    static int answer = 0;

    public static void main(String[] args) throws IOException {
        NM = br.readLine().split(" ");

        for(int i=0; i<Integer.parseInt(NM[0]); i++) {
            list.add(br.readLine());
        }

        for(int i=0; i<Integer.parseInt(NM[1]); i++) {
            String s = br.readLine();
            if(list.contains(s))
                answer++;
        }

        System.out.println(answer);
    }
}

📌 整理する
ArrayList.contains() vs HashMap.containsKey()
1. ArrayList.contains(Object)
ArrayList.contains()呼び出しの場合、ArrayListを巡回し、各要素とオブジェクトが一致するかどうかを比較します.
=>時間複雑度:O(n)
2. HashMap.containsKey(Object)
HashMap.containsKeyを呼び出すと、ハッシュによってオブジェクトがすばやく処理されます.
=>時間複雑度:O(1)