Kawaii Lab

プログラミングとかサービス開発とか

CodilityのLesson2をGoで解いてみた

概要

オンラインコーディングの試験であるCodilityのLesson2を自分なりに解いてみました。 https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

問題の要約

以下の条件で配列が生成される

  • 要素: N個
  • 空ではない
  • 値は必ず奇数
  • 同じ値はペアとして扱う

func Solution(A []int) int は 配列を取得するとペアではない値を返します

アルゴリズムを組み立てる際の情報

  • Nの範囲は[1..1,000,000]
  • 値の範囲は[1..1,000,000,000]
  • 一つを除く全ての値が偶数回発生する(ペアになる)

Sample Data

[9,3,9,3,9,7,9]

コード

package main

import (
 "fmt"
 "os"
)

func main() {
 // 問題文の仮定リスト
 intList := []int{9, 3, 9, 3, 9, 7, 9}

 fmt.Println(`Solo Number:`, Solution(intList))

}

// Solution はN個の要素数と奇数値のみで構成されたInt型の配列を受け取る
// 値の中でペアになっていない値を返却する
func Solution(A []int) int {

 // 配列が空の場合終了
 if len(A) == 0 {
  fmt.Println("Not Include Items in Array")
  os.Exit(1)
 }

 // 重複判別用のmapを作成
 mapForDecidePear := make(map[int]int)

 // 重複した分の数をValueにsetしていく
 // 要素が偶数の場合異常な値として処理
 for _, val := range A {
  if val%2 == 0 {
   fmt.Println("Include Even Number in Array")
   os.Exit(1)
   break
  }

  mapForDecidePear[val] = mapForDecidePear[val] + 1
 }

 // 重複していない要素はValueが1なのでそれを取り出す
 // 重複していない要素は一つしかないので見つかり次第抜けだす
 var soloValue = 0
 for key, val := range mapForDecidePear {
  if val == 1 {
   soloValue = key
   break
  }
 }

 return soloValue
}
結果

Solo Number: 7

解説

重複していない要素を判別する方法として,以下の方法も考えられました

  • 配列に{key,value}の構造体を格納する
  • 配列をsort module を使ってオブジェクトのvalueの順番で並び替える
  • 配列から先頭を取り出して返す

ただ、今回こちらの方法を取ったのは以下の理由になります。

  • 配列を回す回数は変わらないが、sortの中で匿名関数を使う必要があるため、複雑になってしまうこと
  • 構造体を定義する必要がないこと

結論n+1問題を回避すればいいと思うので、特段問題ないと思います。