Java
アルゴリズム
初心者
競技プログラミング

こんにちわ
グローバルセンス株式会社のskanehiraです。

今回はAOJのBinary Searchを解いてみました。
タイトルを見た時に難しいそうだなぁと思いましたが
案外簡単だった…

問題

image.png

要約すると
2行目の数列に4行目の数列の値がいくつ含まれているかを出力しろ
という内容です。

ソース

正直1,3行目の入力は要らないかなぁ…
わざわざスキップする処理を入れたくないので。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        try (Scanner scan = new Scanner(System.in)) {
            // スキップ
            scan.nextLine();

            // 検索対象をmapに格納する
            Map<String, String> map = new HashMap<String, String>();
            for (String num : scan.nextLine().split(" ")) {
                map.put(num, "");
            }

            // スキップ
            scan.nextLine();

            // 検索対象が存在する場合はカウントする
            int count = 0;
            for (String num : scan.nextLine().split(" ")) {
                if (map.containsKey(num)) {
                    count++;
                }
            }

            System.out.println(count);
        }

    }

}

解き方

for (int i : targetNums) {
    for (int j : nums) {
        if (i = j) count++;
    }
}

2行目と4行目を配列に格納して
ぐるぐる回しながら比較すれば行けるかなぁと思ったのですが
for文を2重にするのは効率悪いなので
mapを使うことにしました。

検索対象をmapのキーにしてキーチェックをした方が処理が早いはず!(検証はしていないが)

他にもっと効率良いやり方ないかな…