数字の各桁を足して合計が大きい順に並び替える

Question

今現在、ネットで見つけたC言語の問題を解いているのですが、知識面と技術面が足りなくて、なかなか思うようにかけません。
問題は、
入力した五つの数字、それぞれ各桁を足して合計を求め、合計が大きい順（降順）に並び替える、（但し和が同じ場合は元の数字が小さい方が先）という問題です。
例えば
input
1919810
87654312
29393091
12345678
94789487

上記の数字ぞれぞれの各桁の和は29,36,36,36,56で更に元の数字が小さい方が先ということも考慮すると
output
94789487
12345678
29393091
87654312
1919810
という出力になります。

元の数字の各桁の和を求めて、和を降順にしたコードは書けたのですが、この問題は和の降順を出力するのが問題ではなく、それぞれ各桁の和を求めて和が大きい元の数字を並び替えるもので、そこがうまく書けません。

どなたかヒントをいただけたら嬉しいです。私はどの分野の知識が足りてないですか？

#include <stdlib.h>
int cmpnum(const void * n1, const void * n2)
{
	if (*(int *)n1 > *(int *)n2)
	{
		return -1;
	}
	else if (*(int *)n1 < *(int *)n2)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
int main(){
    int num,dig,N,arr[100];
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&num);//1919810 87654312 29393091 12345678 94789487
    int sum=0;
    while(num){
    dig = num % 10;//各桁の値を求める
    sum = sum + dig;//各桁をたす
    num = num / 10;
    
    }
    arr[i]=sum;
   }
   qsort(arr, N, sizeof(arr[0]), cmpnum);
   for (int i = 0; i < N; i++) 
   printf("%d ", arr[i]);
   printf("\n");

return 0;
}

Answer 1

自分だったらどうするか、という形での回答をさせていただきます。

自分であれば以下の構造体を作ります。

struct CombNumberSum {
    int number;    // 入力した数字を格納
    int sum;       // 入力した数字の桁の合計
}

ヒントが欲しいということなので、この程度の回答とさせていただきます。

Comments

[wanwanko]

ありがとうございます！構造体を使って模索したいと思います！！！

[episteme]

「私はどの分野の知識が足りてないですか？」のコタエになってるかしら?

[wanwanko]

素直に実装するというのが答えかと思いました

[rinjinto]

不足してるものは「発想力」だと判断しました。
これは経験を積んでいくことで培われることが可能なものです。
ですので、ヒントを出してそこから想像してもらうことで発想力を培ってもらおうと思いました。

ベストアンサーにされた実装は実は問題点があります。
それに気付けるでしょうか？

[rinjinto]

(問題点というほど大きなものではないですね。)

[episteme]

つまりは 「足りないのは知識ではない」ってことです。

[episteme]

構造体を定義するこの実装にも問題点があります。
それに気付けるでしょうか？

Answer 2

足りないのは、知識ではなく、思考力だと思います。

桁の和の配列を作ってそれをソートしようとしても、和が同じ場合、元の数が必要です。
元の数とその桁の和という、2つの値をひとまとめにして配列にしないと
いけないと考えるのが普通です。

2つの値をひとつにまとめるのに、構造体の知識があればそれを使えます。
その構造体の配列を用意すればいいのです。

2つの値がともに int であることを考えれば、要素数 2 の配列でも構いません。
その配列の配列を用意すればいいのです。

あと必要な知識は、配列とポインタの関係でしょう。

#include <stdio.h>   // scanf, printf
#include <stdlib.h>  // qsort

int cmpnum(const void *n1, const void *n2)
{
	int *a = (int*)n1, *b = (int*)n2;
	if (a[0] < b[0]) return 1;
	if (a[0] > b[0]) return -1;
	if (a[1] < b[1]) return -1;
	if (a[1] > b[1]) return 1;
	return 0;
}

int main(void)
{
	int num, N, arr[100][2];
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &num);
		arr[i][1] = num;
		arr[i][0] = 0;
		while (num) {
			arr[i][0] += num % 10;
			num /= 10;
		}
	}
	qsort(arr, N, sizeof(arr[0]), cmpnum);
	for (int i = 0; i < N; i++)
		printf("%d ", arr[i][1]);
	printf("\n");
	return 0;
}

このコードは理解できますか？

追記
2つの値(32ビットint)をひとつにまとめるのに、long long(64ビット) を
使うことを考えてみましょう。
和は降順、数値は昇順ですから、和を符号反転すると、比較関数が簡単になります。

#include <stdio.h>   // scanf, printf
#include <stdlib.h>  // qsort

int cmpnum(const void *n1, const void *n2)
{
	long long a = *(long long *)n1, b = *(long long *)n2;
	return a < b ? -1 : a > b;
}

int main(void)
{
	int num, N;
	long long arr[100];
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &num);
		long long sum = 0;
		for (int n = num; n; n /= 10) sum += n % 10;
		arr[i] = -sum << 32 | num;  // 和は降順、数は昇順
	}
	qsort(arr, N, sizeof(arr[0]), cmpnum);
	for (int i = 0; i < N; i++)
		printf("%lld ", arr[i] & 0xffffffff);
	printf("\n");
	return 0;
}

Comments

[wanwanko]

わかりやすくコードを提供してくださりありがとうございます????

[wanwanko]

あの、arr[i] = -sum << 32 | num; の行って何をしている行ですか？

[kazuma-s]

64ビットの long long の上位 32ビットに和の符号を変えたものを置いて、下位32ビットに元の数を置いています。ビット演算の知識はまだないということですか？

最初の配列の配列を使うほうのコードは理解できたのでしょうか？

Answer 3

「それぞれ各桁を足して合計を求め、合計が大きい順（降順）に並び替える、
（但し和が同じ場合は元の数字が小さい方が先）」を素直に実装:

#include <stdio.h>
#include <stdlib.h>

int sum_digit(int num) {
    int sum=0;
    while(num){
      int dig = num % 10;//各桁の値を求める
      sum = sum + dig;//各桁をたす
      num = num / 10;
    }
    return sum;
}

int cmpnum(const void * n1, const void * n2) {
    // 各桁の和が
    int d1 = sum_digit(*(int *)n1);
    int d2 = sum_digit(*(int *)n2);
    // 大きい方が先
    if ( d1 > d2 ) return -1;
    else if ( d1 < d2 ) return 1;
    else { // 同じなら、
      //      元の数が小さい方が先
      if (*(int *)n1 > *(int *)n2) return 1;
      else if (*(int *)n1 < *(int *)n2) return -1;
    }
    return 0;
}

int main(){
    int N, arr[100];
    ...
    qsort(arr, N, sizeof(arr[0]), cmpnum);
    ...
    return 0;
}

Comments

[wanwanko]

ありがとうございます！