プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 その1

番兵法

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造の5.2 線形探索の項目では、番兵法が取り上げられていました。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

番兵法は、線形探索の効率化のために用いられる手法です。参考サイトとして、

blog.codebook-10000.com を参照すると良いと思います。

問題

会津大学の競技プログラミングのサイトの問題をこの本は使用しているので、そのサイトでジャッジを受けることが出来ます。

探索 1 | アルゴリズムとデータ構造 | Aizu Online Judge

コード

import java.util.Scanner;

public class ALDS1_4_A {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int []S = new int[n + 1];
        for(int i = 0; i < n; i++) {
            S[i] = scan.nextInt();
        }
        int q = scan.nextInt();
        int []T = new int[q];
        for(int i = 0; i < q; i++) {
            T[i] = scan.nextInt();
        }
        scan.close();
        int sum = 0;
        for(int i = 0; i < q; i++) {
            if(search(S, n, T[i]) == 1) {
                sum ++;
            }
        }
        System.out.println(sum);
    }
    public static int search(int A[], int n, int key) {
        int i = 0;
        A[n] = key;
        while(A[i] != key) {
            i ++;
        }
        if(i != n) {
            return 1;
        }
        return 0;
    }
}