LoginSignup
0

More than 5 years have passed since last update.

AOJのBinary Searchを解いてみた

Posted at

こんにちわ
グローバルセンス株式会社の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のキーにしてキーチェックをした方が処理が早いはず!(検証はしていないが)

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0