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

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

ただいまの
回答率

90.62%

  • Java

    13478questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

和が7の倍数となる3つの数字の組み合わせを効率よく数えたいです。

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 203

Stars1024

score 1176

いくつかの数字が集まったデータあります。
例えば、{1,5,4,48,4,2,33,5,2,4,2,1,52,3,2,1,4}のような感じです。
ここから7の倍数となる3つの数字の組み合わせがいくつあるか数えたいです。

 私の現在のベストな考え

(I)2重for文を使って7で割ったときの余りがそれぞれいくつかあるか数えます。

  //受け取ったデータを7で割った余りに変換しました。
   int []count = new int[7];
   for(int i = 0; i < data.length; i++){
       for(int j = 0; j < 7; j++){
           if(data[i] == j){
               count[j]++;
           }
       }
   }


(II)和が7の倍数となる組み合わせは
(i)(0 0 0), <-すべて同じ数字
(ii)(0 1 6),(0,2,5),(0,3,4),(1,2,4),(3,5,6) <-すべて異なる数字
(iii)(1,1,5),(1,3,3),(2,2,3),(2,6,6),(4,4,6),(4,5,5) <-数字の種類は2つ
のように12通りあります。
7で割った余りが0となる数字の個数がa個の場合
(i)の(0,0,0)は (a)*(a - 1)*(a - 2) / 6 通りと求めることができます。
(ii),(iii)も同様にして場合の数を高校数学I・Aで習った知識で求めることができます。

一応、これで組み合わせの個数を求めることはできますが、データが多くなると
非効率だと感じました。
特に最初、7で割ったときの余りをそれぞれ数えるところでデータの個数がN個の時
2重for文で N * 7回もループするのでループする回数を減らすことができたら、さらに効率よく求まると思いました。しかし、他の方法は全く思いつかず,これが今の精一杯です。
どなたか、もっと効率の良い方法がありましたら、ご教授できないでしょうか?
もしかしたら、根本から変えるべきかもしれません。
よろしくお願い致します。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+2

(1)のforは1重で捌けます。

   int []count = new int[7];
   for(int i = 0; i < data.length; i++){
       count[data[i] % 7]++;
   }

そして、「二重ループ」といっても、片方の回数が7と固定なので、計算理論上はO(n)(データ量比例)という扱いです。そんなに気にしなくて構いません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/29 18:06

    言われてみれば、(i)のfor文は2重にしなくてもいいと気づきました。
    こういう考え方が重要だと改めて感じました。
    また、O(n) (データ量比例)という語句を知ることもできました。
    おかげで、効率よく求めることができました。
    回答ありがとうございました。

    キャンセル

+1

大筋にはいいと思いますが、重大な問題があります。
例示されたデータを7で割った余りで分類すると次のようになります。

0:         →0個
1: 1,1,1   →3個
2: 2,2,2,2 →4個
3: 52,3    →2個
4: 4,4,4,4 →4個
5: 5,33    →2個
6: 48      →2個


(II)の方法で(1,2,4)の組を作るとき、個数だけカウントしたものの掛け算をした場合、
3*4*4=48通りになりますが、現実には{1,2,4}の1通りのみです。
これは、それぞれの1,2,4を別個のものとして数えたため、大量の重複が発生したためです。

なので、7で割った余りで分類した後、それぞれの数字が何個あるかを数えなければいけません。
その分類をするコード例が次です。

//import static java.util.stream.Collectors.*;
Map<Integer, Map<Integer, Long>> map =
            Arrays.stream(data).boxed()
                .collect(groupingBy(i -> i % 7, groupingBy(i -> i, counting())));


これで、余りの数をキーにmapから取ってきて、1個必要なら種類数、2個なら種類数の組み合わせ+2個以上ある数字の個数 というように処理するべきかと。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/30 12:47 編集

    まず、初めに
    誤解を招いてしまい、すみませんでした。
    >3*4*4=48通りになりますが、現実には{1,2,4}の1通りのみです。
    これは、それぞれの1,2,4を別個のものとして数えたため、大量の重複が発生したためです。

    それぞれの数字を一枚のカードと考えるので重複もあり得ます。
    例えば1,2,4がそれぞれ2枚ずつあるとき組み合わせは 2 * 2 * 2 = 8 通りです。

    >7で割った余りで分類した後、それぞれの数字が何個あるかを数えなければいけません。

    すみませんが、(I)の処理であらかじめ受け取ったデータをそれぞれ7で割った余りに
    変換しています。それをカウントしています。

    キャンセル

  • 2018/04/30 12:48

    でも、HashMapを使うということは勉強になりました。回答ありがとうございました。

    キャンセル

+1

解きかたの方針を述べます。

  1. 整数配列を 7 で割った余りで分類する。
  2. 7 を 3 つの整数に分割する方法を列挙する。
  3. 2 の各ケース毎に、1 で求めた情報から組み合わを計算し、それらを合計する。

整数配列から、
7 での 余り -> {数字: 個数}
でグループ分けするコードをかいてみました。

import java.util.HashMap;
import java.util.Map;

public class SampleApp {
    public static void main(String[] args) {
        int[] nums = { 1, 5, 4, 48, 4, 2, 33, 5, 2, 4, 2, 1, 52, 3, 2, 1, 4 };
        // <7 での余り-> <数字 -> 個数>>
        Map<Integer, Map<Integer, Integer>> counts = new HashMap<>();
        for (int n : nums) {
            int r = n % 7;
            if (counts.get(r) == null) {
                counts.put(r, new HashMap<Integer, Integer>());
            }
            Integer count =  counts.get(r).get(n);
            if (count == null) {
                counts.get(r).put(n, 1);
            } else {
                counts.get(r).put(n, count + 1);
            }
        }

        for (int r : counts.keySet()) {
            System.out.println("" + r + ": " + counts.get(r));
        }
    }
}


実行結果

1: {1=3}
2: {2=4}
3: {3=1, 52=1}
4: {4=4}
5: {33=1, 5=2}
6: {48=1}

(0..6) から重複をゆるして和が 7 の倍数になるものは
0 0 0  // 和が 0 になるもの
0 1 6   // 和が 7 になるもの
0 2 5
0 3 4
1 1 5
1 2 4
1 3 3
2 2 3
2 6 6   // 和が 14 になるもの
3 5 6
4 4 6
4 5 5
の様に分類・列挙していくのがよいです。
これはプログラムでも列挙できると思います。

ぜひ 質問文に現れる 7 , 3 といった定数を、変数にして、汎用的なコードを書くことに挑戦してみるとよいと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/30 12:53

    回答ありがとうございます。
    「HashMapを使って解く」勉強になりました。7,3をそれぞれn,mに変えて汎用的なコードが
    書けるようにしてみます。

    キャンセル

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

  • ただいまの回答率 90.62%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Java

    13478questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。