はじめに
SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)の[C - Kaprekar Number]のメモです。
どのような問題だったか
- 入力は、「N, K」（例：436, 2）
- Nの各桁の数字を大きい順に並べる（例：436が与えられた場合、643にする）
- Nの各桁の数字を小さい順に並べる（例：436が与えられた場合、346にする）
- それぞれ並び替えたものを除算した結果を再度並び替えて除算とK回数繰り返した時の数を出力する（1回目643-346=297, 2回目972-279=693。出力は、「693」）
詳細は、C - Kaprekar Numberにてご確認ください。
主に求められるポイントは以下で、ほぼ言語仕様への理解が必要な問題です。
- 入力された数値を各桁ごとに分解できること
- 数字の降順ソートができること
- 数字の昇順ソートができること
- ソート結果は最終的に数値であること（計算ができること）
解答
２つ提出しました。
- 提出コード①「入力された数値を各桁ごとに分解してソート」
- 提出コード②「入力された数値を文字列に変換し、各桁ごとに分解してソートした後数値に戻す」
愚直に考えると①ですが、数学的知識（3桁の数字から各桁の数値を取り出す）が必要です。
②は文字列にすることで、stringsが使えるためint型より扱いが容易になります。コードも②の方がすっきりしました。
以下は、公式解説のコメントより
問題文に指示された通りの3つの関数を作成し、数列を順に計算していけばよいです。
g1及びg2の計算は多くの言語では「数値を文字列に変換してからソートし、数値に戻す」とすると容易です。
提出コード①
入力された数値を各桁ごとに分解してソートします。
package main
import (
"fmt"
"sort"
"strconv"
)
func main() {
var n, k int
fmt.Scan(&n, &k)
a := n
// k回f(x)を繰り返した残り
for i:=0; i < k; i++ {
a = f(a)
}
fmt.Println(a)
}
// 数値→Slice
func intToSlice(n int) []int {
n_sli := []int{}
// 10で割ったあまり=1の位（723%10は3）
for n > 0 {
n_sli = append(n_sli, n%10)
n /= 10
}
return n_sli
}
// Slice→数値
func sliceToInt(ns []int) int {
n_str := ""
for _, v := range ns {
n_str += strconv.Itoa(v)
}
n_int, _ := strconv.Atoi(n_str)
return n_int
}
// 降順
func g1(x int) int {
xx := intToSlice(x)
sort.Sort(sort.Reverse(sort.IntSlice(xx)))
return sliceToInt(xx)
}
// 昇順
func g2(x int) int {
xx := intToSlice(x)
sort.Ints(xx)
return sliceToInt(xx)
}
func f(x int) int {
return g1(x) - g2(x)
}
コード長：923 Byte
実行時間：188 ms
メモリ：6604 KB
所感
ソートの書き方が複雑すぎる
①②共にですが、降順ソートの書き方の難解さに圧倒されます。
sort.Sort(sort.Reverse(sort.IntSlice(xx)))
文字列と違い、容易に分割することができない
自前で数値→Slice（intToSlice）を用意しています。
ソートするためには、まずXX桁の数値をXX個の要素にする必要がありますので、Sortが使えるスライスに変化します。
コメントに記載していますが、以下の方法により1桁ごとの値を取得できます。
入力例）732
1の位、732÷10=73あまり2 →あまりをスライス[0]に格納
先の計算の解を使って10の位、73÷10=7あまり３ →あまりをスライス[1]に格納
先の計算の解を使って100の位、7÷10=0あまり7 →あまりをスライス[2]に格納
先の計算の解が0になったら終了
出力、int[2, 3, 7]
結合も容易にできない
自前でSlice→数値（sliceToInt）を用意しています。
最終的に除算するので、ソートされたスライスをint型にする必要がありますが、
単純に要素を足していくと数値型は、2+3+7=12となってしまいます。
そのため、一度文字列にして"237"を作成した後、文字列→数値に変換しています。
提出コード②
入力された数値を文字列に変換し、各桁ごとに分解してソートした後数値に戻す
なお、このやり方は一般的ですが、文字列での比較となるので、[2,11,8]など桁数が異なるものが与えられている場合、昇順[2,8,11]としたいところが昇順[11,2,8]となってしまうので使えません。
package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
func main() {
var n, k int
fmt.Scan(&n, &k)
a := n
// k回f(x)を繰り返した残り
for i:=0; i < k; i++ {
a = f(a)
}
fmt.Println(a)
}
// 降順
func g1(x int) int {
n_sli := strings.Split(strconv.Itoa(x), "") // 文字列→Slice
sort.Sort(sort.Reverse(sort.StringSlice(n_sli)))
n_int, _ := strconv.Atoi(strings.Join(n_sli, "")) // Slice→数値（文字列）
return n_int
}
// 昇順
func g2(x int) int {
n_sli := strings.Split(strconv.Itoa(x), "") // 文字列→Slice
sort.Strings(n_sli)
n_int, _ := strconv.Atoi(strings.Join(n_sli, "")) // Slice→数値（文字列）
return n_int
}
func f(x int) int {
return g1(x) - g2(x)
}
コード長：786 Byte
実行時間：167 ms
メモリ：6592 KB
所感
ソートの書き方は数値型か文字型かでメソッド名は異なるが、基本変わらず
sort.Ints([]int) //int型スライス
sort.Strings([]string) //string型スライス
文字列→スライス（string型→[]string型）が容易
n_sli := strings.Split(strconv.Itoa(x), "")
strconv.Itoa(int)で、入力数値→文字列の変換をしています。
変換したらstrings.Split(string, "")が使えるので、区切り文字なし（1桁ごと）でスライスできます。
※数値にこのようなメソッドはないようです。
スライス→文字列（[]string型→string型）が容易
n_int, _ := strconv.Atoi(strings.Join(n_sli, ""))
strings.Join([]string, "")を使うと、スライスの要素を区切り文字なし（1桁ごと）で文字列にできます。
※Split同様、数値にこのようなメソッドはないようです。
最後に計算のため、strconv.Atoi(string)で、文字列→数値の変換をしています。
おわりに
並び順をどうにかする問題、毎回ぐるぐる考えてしまうのでどうにかしたいです。
追記
コメントでいただいた[]stringではなく[]byteでソートするやり方が一番きれいではやい！