Insertion Sort

もう一回おさらいということでプログラミングコンテスト攻略のためのアルゴリズムとデータ構造を購入しました。

package main

import (
    "fmt"
    "strings"
)

func scanInput() (n int, slice []int) {
    fmt.Scanf("%d", &n)
    slice = make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scanf("%d", &slice[i])
    }
    return
}

func printSlice(slice []int) {
    fmt.Println(strings.Trim(strings.Join(strings.Fields(fmt.Sprint(slice)), " "), "[]"))
}

func main() {
    _, slice := scanInput()

    printSlice(slice)

    solve(slice)
}

func solve(nums []int) {
    l := len(nums)
    for i := 1; i < l; i++ {
        v := nums[i]
        j := i - 1
        for j >= 0 && nums[j] > v {
            nums[j+1] = nums[j]
            j--
        }
        nums[j+1] = v

        printSlice(nums)
    }
}

ロジックよりも、入力を受け取る実装で戸惑いました。
プログラミングパズルは言語の筋トレにもなっていいですね。

参考

https://stackoverflow.com/questions/37532255/one-liner-to-transform-int-into-string

2020-03-07

参考