久々に、アルゴリズムの問題を解いてみました。
ソースは、とある大学の課題です。
問題
多次元配列にある要素のうち、重複がある要素数をカウントしなさい。
例1:
入力:
出力:2
例2:
入力:
出力:1
例3:
入力:
出力:5
前提条件
- C言語で解くこと。(めんどい。)
- 多次元配列には、-99999以外の数値を入力すること。
- 多次元配列のサイズは、ハードコーディングとして、多次元配列の要素をキーボード入力としている。
考えたアルゴリズムの流れ
- 入力した多次元配列の全要素のうち、重複する要素を入れるリスト(以降、重複リスト)と重複しない要素を入れるリスト(以降、非重複リスト)をそれぞれ用意する。
- 入力した多次元配列の全要素をループ参照して、重複リスト、非重複リストにそれぞれ以下の条件で格納する。
- 重複リストに参照した多次元配列の要素がマッチすれば、すでにカウント済みの要素のためSKIPする。
- 重複リストに、マッチする要素がなければ、非重複リストにマッチするか調べる。
- 非重複リストにマッチする要素があれば、重複カウンタを更新して、該当要素を重複リストに追加および、非重複リストから削除する。
- 非重複リストにマッチする要素なければ、非重複リストに該当要素を追加する。 3.重複したカウントを出力する。
実装コード
#include<stdio.h>
#define SUB 2
#define NUM 5
/*
* 配列listにtargetNumが含まれてれば該当するindexを返却,
* 含まれていなければ-1を返却
*/
int find(int targetNum, int search_size, int *list)
{
for(int i=0;i<search_size;++i)
{
if(list[i] == targetNum)
{
return i;
}
}
return -1;
}
int main(void)
{
int test[SUB][NUM];
int non_dxs[SUB*NUM]; // testのうち非重複値を格納した配列
int dxs[SUB*NUM]; //testのうち重複値を格納した配列
int i;
int j;
int sum=0;
const int invalid = -99999;
printf("五個の整数の組を二組入力して下さい\n");
for(i=0;i<SUB;i++)
{
for (j = 0; j< NUM; j++)
{
printf("test[%d][%d]:", i + 1, j + 1);
//scanf_s("%d",&test[i][j]);
scanf("%d",&test[i][j]); // macはこっちで動く
//dxs, non_dxsの初期化
dxs[i*NUM + j] = invalid;
non_dxs[i*NUM + j] = invalid;
}
}
int dxIdx = 0;
int nonIdx = 0;
int retIdx;
for(i = 0; i < SUB; i++)
{
for(j = 0; j < NUM; j++)
{
//重複値を探索
if(find(test[i][j], dxIdx, dxs) == -1)
{
//重複値がない場合、非重複値を検索
retIdx = find(test[i][j], nonIdx, non_dxs);
if(retIdx >= 0)
{
//非重複値での検索がtrueの場合は、非重複から要素を除去
non_dxs[retIdx] = invalid;
//重複リストにあらたな要素を格納
dxs[dxIdx++] = test[i][j];
//sumをインクリメント
sum = sum + 1;
}
else
{
//非重複値に要素がない場合は、非重複値のリストを更新する。
non_dxs[nonIdx++] = test[i][j];
}
}
}
}
if (sum == 0)
{
printf("2つの組の整数で同じ整数はありません\n");
}
else
{
printf("2つの組の整数で同じ整数の個数は%d個です\n", sum);
}
getchar();
getchar();
return 0;
} //main
感想
- 久々に、純粋なアルゴリズムをC言語で解いた。
- 結構時間かかった。。。私の中で、Pythonのゆとり教育が相当進んでいるものと思われる。
- たまにはこういう問題を解いてみるのも悪くない。
お願い
もっと効率の良い解き方があるなどご意見があれば、お願いします！