ALDS1_4_A 線形探索をC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文

n 個の整数を含む数列 S と、q 個の異なる整数を含む数列 T を読み込み、T に含まれる整数の中で S に含まれるものの個数 C を出力するプログラムを作成してください。

入力
1行目に n、2行目に S を表す n 個の整数、3行目に q、4行目に T を表す q 個の整数が与えられます。

出力
C を1行に出力してください。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_A

解答

その1(2021/07/05に追記)

#include <bits/stdc++.h>
using namespace std;

bool linear_search(int S[], int n, int key) {
    int i = 0;
    S[n] = key;
    while(S[i] != key) {
        i++;
    }
    if(i == n) {
        return false;
    } else {
        return true;
    }
}

int main() {
    int n;
    cin >> n;
    int S[n];
    for(int i = 0; i < n; i++) {
        cin >> S[i];
    }
    int q;
    cin >> q;
    int T[q];
    for(int i = 0; i < q; i++) {
        cin >> T[i];
    }
    int count = 0;
    for (int i = 0; i < q; i++) {
        if (linear_search(S, n, T[i])) {
            count++;
        }
    }
    cout << count << endl;

    return 0;
}

その2

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int S[n];
    for(int i = 0; i < n; i++) {
        cin >> S[i];
    }
    int q;
    cin >> q;
    int T[q];
    for(int i = 0; i < q; i++) {
        cin >> T[i];
    }
	vector<int> count;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < q; j++) {
            if(S[i] == T[j]) {
				count.push_back(T[j]);
            }
        }
    }
	sort(count.begin(), count.end());
	count.erase(unique(count.begin(), count.end()), count.end());
	cout << count.size() << endl;

    return 0;
}

感想

追記(2021/07/05)

一般解説を参考に書き直しました。

配列と配列をループで比べるのではなく、関数にわけるとわかりやすいですね…。

番兵という考え方もこういうやり方で効率があがることに納得しました。

linear_search関数の戻り値について、若干の疑問があります。

番兵のあるコードでは、真偽値を返せばいいのですが、一般解説にある関数の書き方ですと、見つかった配列の添字か、-1などの値を返せばいいのだろうか、と悩みます。

その2のコードは、問題の趣旨とも若干はずれてる気がするので、参考にする方はその1のコードを参考にされた方がいいかと思います。

最初の解答について

2つの配列に値をつめてそれぞれ比較すればいいのかと思いましたが、重複の値があるので単純ではありません。

いい方法が浮かばずにベクター配列に値をつめて、重複を削除しています。

重複の削除は、最初の入力の段階でやって、あとは比較したものをカウントするのでもいいです。

複数配列、複数添字の処理のしかたは、なかなかしっかり理解できません。

まとめ

AIZU ONLINE JUDGEの「ALDS1_4_A 線形探索」を解いてみましたので、その回答と解説をご紹介いたしました。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント(@mnbbbbbd

以上です。
読んでいただきありがとうございました!