AtCoder Beginner Contest 192 C - Kaprekar Number（Golang）

#はじめに
[SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)](https://atcoder.jp/contests/abc192)の[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](https://atcoder.jp/contests/abc192/tasks/abc192_c)にてご確認ください。
主に求められるポイントは以下で、ほぼ言語仕様への理解が必要な問題です。

- 入力された数値を各桁ごとに分解できること
- 数字の降順ソートができること
- 数字の昇順ソートができること
- ソート結果は最終的に数値であること（計算ができること）

##解答
２つ提出しました。

- 提出コード①「入力された数値を各桁ごとに分解してソート」
- 提出コード②「入力された数値を文字列に変換し、各桁ごとに分解してソートした後数値に戻す」

愚直に考えると①ですが、数学的知識（3桁の数字から各桁の数値を取り出す）が必要です。
②は文字列にすることで、stringsが使えるためint型より扱いが容易になります。コードも②の方がすっきりしました。
以下は、[公式解説](https://atcoder.jp/contests/abc192/editorial/688)のコメントより
> 問題文に指示された通りの3つの関数を作成し、数列を順に計算していけばよいです。
g1及びg2の計算は多くの言語では「数値を文字列に変換してからソートし、数値に戻す」とすると容易です。

##提出コード①
入力された数値を各桁ごとに分解してソートします。

```golang
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]となってしまうので使えません。

```golang
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

###所感
#####ソートの書き方は数値型か文字型かでメソッド名は異なるが、基本変わらず

```golang:昇順ソート
sort.Ints([]int) //int型スライス
sort.Strings([]string) //string型スライス
```
#####文字列→スライス（string型→[]string型）が容易
```golang:②から抜粋
n_sli := strings.Split(strconv.Itoa(x), "")
```

`strconv.Itoa(int)`で、入力数値→文字列の変換をしています。
変換したら`strings.Split(string, "")`が使えるので、区切り文字なし（1桁ごと）でスライスできます。
※数値にこのようなメソッドはないようです。

#####スライス→文字列（[]string型→string型）が容易
```golang:②から抜粋
n_int, _ := strconv.Atoi(strings.Join(n_sli, ""))
```

`strings.Join([]string, "")`を使うと、スライスの要素を区切り文字なし（1桁ごと）で文字列にできます。
※Split同様、数値にこのようなメソッドはないようです。
最後に計算のため、`strconv.Atoi(string)`で、文字列→数値の変換をしています。


##おわりに
並び順をどうにかする問題、毎回ぐるぐる考えてしまうのでどうにかしたいです。

##追記
コメントでいただいた[]stringではなく[]byteでソートするやり方が一番きれいではやい！