AtCoderを始めてから配列操作をすることが多く、解説やユーザーの回答でも配列の操作で割り算の余りを使っている場面が多々あり、割り算の余りって使えるんだ〜と思ったので、自分なりに復習したことを書いてみます。
配列の範囲＝割り算の余りの範囲だから便利
長さNの配列と、ある自然数をNで割った余りは、同じ範囲を取りますよね。
これが配列操作で割り算の余りを使うと便利な理由だと思います。
例：要素数がNの配列のインデックスの範囲（N=5）
// arrのインデックスの範囲＝0〜4、すなわち、0〜(N-1)
arr := []int{1, 2, 3, 4, 5}
例：自然数をNで割った余り（N=5）
5%5=0, 1%5=1, 2%5=2, 3%5=3, 4%5=4
割り算の余りが取る範囲＝0〜4、すなわち、0〜(N-1)
上記のとおり、両者の取る範囲が同じであることから、配列と割り算の余りは相性が良いということですね。
配列を右回りにRotateする
割り算の余りを使って、配列を右にRotateする例を考えてみたいと思います。
package main
import "fmt"
func main() {
n := 7 // 配列のサイズ
k := 3 // 右に回転する数
arr := []int{1, 2, 3, 4, 5, 6, 7}
rotated := make([]int, n)
for i := 0; i < n; i++ {
rotated[(i+k)%n] = arr[i]
}
fmt.Println(rotated) // [5 6 7 1 2 3 4]
}
まず、「i+k」で現在位置にある要素をk個分右にずらします。
しかし、そのままだと配列を飛び出てしまうことがあるので、「%n」で位置を決定します。
※左回りの場合は、インデックスがマイナスになるので、その分を一度割り算の余りを使って0に近づけてから、位置付けると考えると良いと思います。
例：k = (k%n+n)%n
左回転する場合は、kにマイナスの値を入れることになります。
例：左に123回転する
package main
import "fmt"
func main() {
n := 7 // 配列のサイズ
k := -123 // 回転する数
arr := []int{1, 2, 3, 4, 5, 6, 7}
k = (k%n + n) % n // 正の回転量に変換
rotated := make([]int, n)
for i := 0; i < n; i++ {
rotated[(i+k)%n] = arr[i]
}
fmt.Println(rotated)
}
配列操作における、割り算の余りの使い所は、位置付けということですね。
この位置付けの例として、グルーピングも考えられるので、やってみたいと思います。
割り算の余りを使ったグルーピング
インデックスiを使って、k個のグループに要素を分けていく処理を考えます。
package main
import "fmt"
func main() {
n := 8
k := 3
arr := []int{3, 1, 4, 1, 5, 9, 2, 6}
groups := make([][]int, k)
for i := 0; i < n; i++ {
groups[i%k] = append(groups[i%k], arr[i])
}
fmt.Println(groups) // [[3 1 2] [1 5 6] [4 9]]
}
元の要素をk間隔で、groupsに位置付けることができました。
しかし、ランダムにグルーピングしたい場面とかあるかもと思ったので、試してみました。
ランダムにグルーピングしてみる
配列の要素をランダムにグルーピングしてみます。
package main
import (
"fmt"
"math/rand"
)
func main() {
data := []string{"ナルト", "サスケ", "サクラ", "孫悟空", "孫悟飯", "クリリン", "ピッコロ", "バカボン", "バカボンのパパ", "はじめちゃん"}
groupCount := 3 // グループ数
groups := make([][]string, groupCount)
// データをランダムに割り当て
for _, item := range data {
randomGroup := rand.Intn(groupCount) // 0 ~ (groupCount-1) のランダムな値が入る
groups[randomGroup] = append(groups[randomGroup], item)
}
for i, group := range groups {
fmt.Printf("Group %d: %v\n", i+1, group)
}
}
上記を実行すると、data内の各要素がランダムにgroupsに位置付けられます。
ランダムであるため、グループ内に誰もいないグループができることもあります。
ナルトが一人だけになると悲しいので、誰も1人にならないように、ランダムにグループ化しつつ各グループが均等になるようにしたいと思います。
シャッフルしてグルーピング（番外編）
前回のグルーピングでは、グループ内に誰もいなかったり、一人だけになってしまう寂しい状況ができてしまうため、誰も一人にならないように、各グループが均等になるようにしたいと思います。
package main
import (
"fmt"
"math/rand"
)
func main() {
data := []string{"ナルト", "サスケ", "サクラ", "孫悟空", "孫悟飯", "クリリン", "ピッコロ", "バカボン", "バカボンのパパ", "はじめちゃん"}
groupCount := 3 // グループ数
// 配列をシャッフル
rand.Shuffle(len(data), func(i, j int) {
data[i], data[j] = data[j], data[i]
})
groups := make([][]string, groupCount)
// 均等に割り当て
for i, item := range data {
groups[i%groupCount] = append(groups[i%groupCount], item)
}
for i, group := range groups {
fmt.Printf("Group %d: %v\n", i+1, group)
}
}
これで寂しいグループができなくなりました。
最後に
今週のADTは、配列操作をするようなテーマだったのかな？と思いました。（問題はランダムに選ばれてるのかもしれないけど勝手にそう思いました）
私は、EASYに参加しているのですが、週ごとに課題を見つけるいい機会になっています。
毎日少しずつ問題を解いて、理解して、ABCでより早く正確に回答できるようになりたいです。
まずは茶色になることが目標だあああああああああ！！！！！
(･ω･)ﾏﾀﾈ