AtCoderのGo言語で構造体をソートする時の注意点

この記事は、マイナビ Advent Calendar 2019 17日目の記事となります。

概要

AtCoderのGo言語ジャッジシステムで、構造体のスライスをソートする時の注意点をまとめました。

2通りの方法

• 競技プログラミングでは、ソートをよく使います。
• Go言語にはPackage sortがあります。
• int、float64、string型は、それぞれ以下の関数で簡単にソートできます。
  • sort.Ints
  • sort.Float64s
  • sort.Strings
• しかし上記3つの以外の型をソートする場合は、一工夫必要です。

sort.Slice (バージョン1.8で追加)

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

func main() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)
    sort.Slice(people, func(i, j int) bool {
        return people[i].Age > people[j].Age
    })
    fmt.Println(people)

}

sort.Sort (バージョン1.7以前でも使用可能)

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

func (p Person) String() string {
    return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }

func main() {
    people := []Person{
        {"Bob", 31},
        {"John", 42},
        {"Michael", 17},
        {"Jenny", 26},
    }

    fmt.Println(people)
    sort.Sort(ByAge(people))
    fmt.Println(people)
}

※Package sortのExampleから抜粋

バージョン1.6ではsort.Sliceが使用できない

• sort.Sliceを使う方が明らかにシンプルに書けます。
• しかし、AtCoderのGo言語ジャッジシステムはバージョン1.6のため、sort.Sliceは使用できません。
  • ※2019年12月16日時点
• アップデートがされるまでは、AtCoder提出用のコードはsort.Sortを使う方法で書くしかなさそうです。
  • AtCoderの言語アップデートに関して