こんにちは。KOUKIです。
とあるWeb系企業でGoエンジニアをしています。
Golangでアルゴリズムの学習をしましょう!
今回は、2つの配列を比較して、小さい順に並べ替えた配列を返却するプログラムを書いてみたいと思います。
課題
次の配列(スライスとも呼ぶ)を用意します。
|
1 2 |
array1 := myArray{0, 3, 4, 41} array2 := myArray{4, 6, 30} |
この配列は、小さい数値 -> 大きい数値の順で値が格納されていることをただ一つのルールとしています。一つの配列内のソートであれば、golangのsortパッケージで順番をいじれるので、配列内の数値の並び替えは割愛しました。
2つの配列を比較して、小さい値の順番にソートした一つの配列を戻り値として返すプログラムを実装しましょう。
回答
実装方法はいくつかあると思いますが、私は以下のように実装しました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
package main import ( "fmt" ) type myArray []int func mergeSortedArrays(array1, array2 myArray) myArray { mergeArray := []int{} smallArray := []int{} largeArray := []int{} largeArrayItem := 0 smallArrayMap := make(map[int]int) smallArrayItem := 0 // 配列が大きさ判定 if len(array1) > len(array2) { smallArray = array2 largeArray = array1 } else { smallArray = array1 largeArray = array2 } // 配列大 -> 小でループ for _, b := range largeArray { for _, s := range smallArray { // 既に追加したyの値は追加したくないのでスキップ if _, ok := smallArrayMap[s]; ok { continue } // 配列の大小チェック if b < s { mergeArray = append(mergeArray, b) smallArrayItem = s break } else if b == s { mergeArray = append(mergeArray, b) break } else { largeArrayItem = b mergeArray = append(mergeArray, s) smallArrayMap[s] = s // 追加したyの値を記録 } } } // 最後に大きい方の数字を入れる if largeArrayItem > smallArrayItem { mergeArray = append(mergeArray, largeArrayItem) } else { mergeArray = append(mergeArray, smallArrayItem) } return mergeArray } func main() { array1 := myArray{0, 3, 4, 41} array2 := myArray{4, 6, 30} fmt.Println( "array1 - array2: ", mergeSortedArrays(array1, array2)) array3 := myArray{3, 9, 34} array4 := myArray{8, 9, 20, 33} fmt.Println( "array3 - array4: ", mergeSortedArrays(array3, array4)) array5 := myArray{1, 3, 6} array6 := myArray{2, 4, 5, 7} fmt.Println( "array5 - array6: ", mergeSortedArrays(array5, array6)) } |
- 配列1と配列2の大きさをチェックする
- 大きい配列(b)から小さい配列(s)をチェックする
- bの値がsの値より小さい場合は、bの値を格納。sの値を一時変数に保存。
- bとsの値が同じである場合はbの値を格納(sでもよい)
- bの値がsの値より大きい場合はsの値を格納し、s, bの値を一時保存変数に格納する。sはmap型。
- sの値を格納した一時保存用の値は既に配列に格納済みなのでmapに値があればスキップする
- 一時保存したbとsの値をチェックし、大きい数値を保存。
|
1 2 3 4 |
$ go run main.go array1 - array2: [0 3 4 4 6 30 41] array3 - array4: [3 8 9 9 20 33 34] array5 - array6: [1 2 3 4 5 6 7] |
OKですね。一応動きましたが、もっといいアルゴリズムがあると思いますので、皆様もぜひチャレンジしてみてください^^
まとめ
アルゴリズムを考えると頭の体操になります。近頃のWeb開発はフレームワークの力で、アルゴリズムを考えなくても実装できてしまいます。
しかし、毎日15分ずつでいいので、自分でアルゴリズムを考える習慣を持つとよりHappyなエンジニアライフを送れると思います。
それでは、また!
Go記事まとめ
ソースコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
package main import ( "fmt" ) type myArray []int func mergeSortedArrays(array1, array2 myArray) myArray { mergeArray := []int{} smallArray := []int{} largeArray := []int{} largeArrayItem := 0 smallArrayMap := make(map[int]int) smallArrayItem := 0 // 配列が大きさ判定 if len(array1) > len(array2) { smallArray = array2 largeArray = array1 } else { smallArray = array1 largeArray = array2 } // 配列大 -> 小でループ for _, b := range largeArray { for _, s := range smallArray { // 既に追加したyの値は追加したくないのでスキップ if _, ok := smallArrayMap[s]; ok { continue } // 配列の大小チェック if b < s { mergeArray = append(mergeArray, b) smallArrayItem = s break } else if b == s { mergeArray = append(mergeArray, b) break } else { largeArrayItem = b mergeArray = append(mergeArray, s) smallArrayMap[s] = s // 追加したyの値を記録 } } } // 最後に大きい方の数字を入れる if largeArrayItem > smallArrayItem { mergeArray = append(mergeArray, largeArrayItem) } else { mergeArray = append(mergeArray, smallArrayItem) } return mergeArray } func main() { array1 := myArray{0, 3, 4, 41} array2 := myArray{4, 6, 30} fmt.Println( "array1 - array2: ", mergeSortedArrays(array1, array2)) array3 := myArray{3, 9, 34} array4 := myArray{8, 9, 20, 33} fmt.Println( "array3 - array4: ", mergeSortedArrays(array3, array4)) array5 := myArray{1, 3, 6} array6 := myArray{2, 4, 5, 7} fmt.Println( "array5 - array6: ", mergeSortedArrays(array5, array6)) } |
にほんブログ村
コメントを残す
コメントを投稿するにはログインしてください。