質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

タイムアウト

タイムアウトはイベント発生から完了までに掛かる経過時間に対する一定の待ち時間を指します。また、特定の時間が経過された場合に発生するイベントを指すこともあります。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

Q&A

解決済

4回答

4607閲覧

2重ループが原因でタイムアウトになるコードを改善したい

qazwsx_0000

総合スコア6

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

タイムアウト

タイムアウトはイベント発生から完了までに掛かる経過時間に対する一定の待ち時間を指します。また、特定の時間が経過された場合に発生するイベントを指すこともあります。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

0グッド

0クリップ

投稿2020/02/05 16:49

編集2020/02/06 09:07

C言語初心者です。以下の問題で困っています。
(問題)
2つの英字小文字のみからなる長さがそれぞれn,mの文字列s1(文字数n),s2(文字数m)が与えられたとする。文字列s1に含まれる文字を使って文字列s2を作ろうとしたとき足りなくなる文字の個数を表示せよ。ただし文字列を構成する文字は1度のみ使うことができる。
1<=n<=100000,1<=m<=100000

たとえば文字列s1="catfood" s2="carrot" であるとき、s2を作るにはs1にある文字c,a,tとoが一つ使えるので必要なのはrが2つとなり出力は2になります。

これをC言語で表現しようとして考えたアルゴリズムが、文字列s2の先頭の文字から最後まで順に文字列s1の要素と比較し、等しければ両方の文字列の要素を0で上書きする。これを文字列s1の要素の最後まで行い、最後に文字列s2を出力して0でない要素の個数を出力する。
例えば上記であれば最終的にs1="000f0od" s2="00rr00"となり文字列s2の0ではない要素数である2が出力されます。

コードは以下になります。
これを実行すると小規模データは結果を出力しますがn^2のオーダーのためか要素が 100000の文字列ではタイムアウトになります。

アルゴリズムが悪いのか配列以外のデータ構造を使う必要があるのか考えてもわかりません。改善点をご教授いただければ幸いです。

C

1#include <stdio.h> 2int n,m; 3char s1[100000]; 4char s2[100000]; 5//文字列s2の各要素を文字列s1の要素と比較し等しければその2つの要素を0で上書きする。 6void compare(char *s1,char *s2){ 7 for(int i=0;i<m+1;i++){ 8 for(int j=0;j<n+1;j++){ 9 if(s2[i]==s1[j]){s2[i]=s1[j]='0';} 10 } 11 } 12} 13//改変された文字列s2の要素のうち0でないものの個数をカウントする。 14int count(char *s2){ 15 int counter=0; 16 for(int i=0;i<m+1;i++){ 17 if(s2[i]!='0')counter+=1; 18 } 19 return counter; 20} 21 22int main(void){ 23 scanf("%d %d",&n,&m); 24 scanf("%s",s1); 25 scanf("%s",s2); 26 compare(s1,s2); 27 printf("%d\n",count(s2)); 28 return 0; 29}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

qazwsx_0000

2020/02/06 09:08

申し訳ありません。 所定の場所に移しました。
guest

回答4

0

ベストアンサー

そのコードでは s1="catfood" s2="carroot" の時は幾つになるでしょう.

100000文字は試していません.

c

1#include <stdio.h> 2#include <string.h> 3 4//'a'~'z' 5#define SIZE 26 6 7int main(void) { 8 char *s1="catfood"; 9 char *s2="carrot"; 10 11 int a1[SIZE]={0}; 12 int l1=strlen(s1); 13 for(int i=0;i<l1;i++) a1[s1[i]-'a']=1; 14 15 int a2[SIZE]={0}; 16 int l2=strlen(s2); 17 for(int i=0;i<l2;i++) a2[s2[i]-'a']++; 18 19 int r=0; 20 for(int i=0;i<SIZE;i++) if(a2[i]>a1[i]) r+=a2[i]-a1[i]; 21 printf("%d\n",r); 22 23 return 0; 24}

投稿2020/02/05 19:47

編集2020/02/06 04:18
jimbe

総合スコア12545

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kazuma-s

2020/02/06 02:19

タイムアウトが問題なのに、forループの中で strlen を繰り返し呼び出すのはいかがなものでしょうか? s1 には o が 2つあるので、s2 に o が 2つあってもよいのではないでしょうか?
jimbe

2020/02/06 04:21

>forループの中で strlen を繰り返し呼び出す 見えない多重ループになっているということですね. 修正致しました. >s1 には o が 2つあるので、s2 に o が 2つあってもよいのでは >>s2を作るにはs1にある文字c,a,tとoが一つ使える と言われているので, s2 に o が2つあった場合は1つ不足としてカウントされるのではないかと思った次第です.
qazwsx_0000

2020/02/06 09:17

このコードを改変して投稿すると文字列数100000でも0.01秒にて実行されました。 他の方も言われているようにアルファベットのみの文字列であることを利用することで高速化が図れるようです。 ありがとうございました。
guest

0

各文字ごとの個数だけわかれば計算できます。出現位置の情報は無視していいということです。そうすると線形時間で処理できます。

s1とs2ごとに文字:出現数の表を作って、その間で差分を取り(table2[char_i] - table1[char_i]のような形で。ただしマイナスになったら0とみなす)合計するのでしょう。

Pythonでサンプルを示します。

python

1from collections import Counter 2 3s1 = "catfood" 4s2 = "carrot" 5 6table1 = Counter(s1) 7table2 = Counter(s2) 8 9# 確認 10print(table1) 11print(table2) 12 13for key in table2.keys(): 14 x = table2[key] - table1[key] 15 table2[key] = max(x, 0) 16 17# 確認 18print(table2) 19 20# 結果 21print(sum(table2.values())) 22 23""" => 24Counter({'o': 2, 'c': 1, 'a': 1, 't': 1, 'f': 1, 'd': 1}) 25Counter({'r': 2, 'c': 1, 'a': 1, 'o': 1, 't': 1}) 26Counter({'r': 2, 'c': 0, 'a': 0, 'o': 0, 't': 0}) 272 28"""

Cで実装する場合、出現する文字がASCIIだけなら、128要素の整数型配列を使うことができます。マルチバイト文字ならデータ構造を工夫した方が賢いでしょう。

投稿2020/02/05 17:52

編集2020/02/06 10:20
hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

qazwsx_0000

2020/02/06 09:13

出現する文字数を格納する配列を作るとうまく解決しました。 またpythonのCounter関数は勉強になりました。
guest

0

改善点をご教授いただければ幸いです。

のご要望にお応えしていませんが、見つけたら配列から削除する方式です

c

1#include <stdio.h> 2#include <string.h> 3 4char n[100000]; 5char m[100000]; 6 7int main(){ 8 memset(n, '\0', sizeof(n)); 9 memset(m, '\0', sizeof(m)); 10 11 printf("文字列[n]:"); 12 fgets(n, sizeof(n), stdin); 13 n[strlen(n)-1]='\0'; 14 printf("文字列[m]:"); 15 fgets(m, sizeof(m), stdin); 16 m[strlen(m)-1]='\0'; 17 printf("n:%s\n",n); 18 printf("m:%s\n",m); 19 20 int i, j, cnt=0, flg; 21 for(i=0;i<strlen(m);i++){ 22 flg=1; 23 for(j=0;j<strlen(n);j++){ 24 if(m[i] == n[j]){ 25 strcpy(n+j,n+(j+1)); 26 flg=0; 27 break; 28 } 29 } 30 cnt+=flg; 31 } 32 printf("count:%d\n",cnt); 33 return 0; 34}

ご指摘を受けて修正版

c

1#include <stdio.h> 2#include <string.h> 3 4char n[100001]; 5char m[100001]; 6char z[100001]; 7 8int main(){ 9 memset(n, '\0', sizeof(n)); 10 memset(m, '\0', sizeof(m)); 11 12 scanf("%s", n); 13 scanf("%s", m); 14 15 int i, j, cnt=0, flg; 16 int x=strlen(m); 17 int y=strlen(n); 18 printf("n:%d\n",x); 19 printf("m:%d\n",y); 20 21 for(i=0;i<x;i++){ 22 flg=1; 23 for(j=0;j<y;j++){ 24 if(m[i] == n[j]){ 25 strcpy(z,n+(j+1)); 26 strcpy(n+j,z); 27 y--; 28 flg=0; 29 break; 30 } 31 } 32 cnt+=flg; 33 } 34 printf("count:%d\n",cnt); 35 return 0; 36}

私の貧富マシンでも100000件を1分程度で終了しました。

投稿2020/02/05 23:48

編集2020/02/06 04:55
amura

総合スコア333

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kazuma-s

2020/02/06 02:20

タイムアウトが問題なのに、forループの中で strlen を繰り返し呼び出すのはいかがなものでしょうか?
qazwsx_0000

2020/02/06 10:16

このコードでも100000の文字列を30秒でクリアします。私のコードは3分以上かかるようです。 教えていただきたいのですが、私のコードでもこのコードでもfor文を用いた2重ループで、私の場合配列の上書き、このコードの場合配列をずらしています(コピーしています)。ループの最後に行う処理はあまり違いがないように思うのですが私のコードで3分以上かかる処理をこのコードが早く処理できるのはなぜなのでしょうか?
amura

2020/02/06 10:34

多分strcpyでのデータ移動の方が効率が良かったのではないでしょうか? strcpyは1バイトづつの転送ではないらしく、最初のプログラムで10万件行うと答えが変になります。後のプログラムでは2回コピーしています。
qazwsx_0000

2020/02/06 11:13

確かに私の環境でも最初のコードは大規模データで失敗しました。strcpyのマニュアルをみると「コピー元とコピー先が重なり合う場合動作が未定義」とありますが、大規模データでのバグに関係しているかもしれませんね。 他の方のアルファベットの特性を利用したコードがこの問題の正解に近いものだとは思いましたのでベストアンサーにしましたが、amuraさんのコードは非常に勉強になりました。ありがとうございました。
guest

0

ルールの内で時間を短縮するのに有用なのは

  • 英字小文字のみからなる
  • 文字列を構成する文字は1度のみ使うことができる

ですね。

s1 がどれだけ長かろうと出来上がる情報量は 26bit (英字小文字は 26 文字なので) しかありません。 一度しか使えないので何度現れても「使われているかどうか」だけの情報があればよいのです。

  • まずは s1 を走査して各アルファベットが使われているかどうかを調べる
  • 調べた値が s2 にも出現しているか調べる
  • s1 にも s2 にも表れている文字種の数を s2 の長さから引く

でどうでしょう。

これなら O(n+m) のオーダーで解決できると思うのですが。

投稿2020/02/05 17:42

SaitoAtsushi

総合スコア5437

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

qazwsx_0000

2020/02/06 09:11

確かに英字小文字のみという条件でしぼると解決できます。 ありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問