1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

ABC049C - 白昼夢を簡単に導く方法が知りたい(Golang)

Last updated at Posted at 2020-02-11

##はじめに
ABC049C - 白昼夢を検索文字列の特性上、文字列をリバースして導く方法で解きました。
解きかたは模範解答とされている手法なのでさておき、
こちらをGoで実現しようとしたとき検索能力の低さゆえ、Goに以下の機能が見つけられず手作りとなってしまったので、改良したいと思いメモです。

  • 文字列のリバース
  • 開始〜終了桁数を指定した文字列の抜き出し(例:abcを1文字目から2文字目で抜き出して「b」を求める)

##提出コード

package main

import (
  "fmt"
)

func main() {
  var s string
  annwer := "YES"
  divide := [4]string{"dream", "dreamer", "erase", "eraser"}
  fmt.Scanf("%s", &s)
  
  // リバース
  for i :=0; i < len(divide); i++ {
    divide[i] = getReverse(divide[i])
  }
  reverse := getReverse(s)
  
  // 後ろから一致するものを抜き出す
  j := 0 // 開始位置
  for j < len(reverse) {
    annwer = "NO"
    for i := 0; i < 4; i++ {
      
      // 比較する文字列を必要な範囲で抜き出す
      var str string
      for k := j; k < j + len(divide[i]); k++ {
        if k >= len(reverse) {
          continue
        }
        str += string(reverse[k])
      }
      // 比較
      if str == divide[i] {
        // 一致した分開始位置をずらす
        j += len(divide[i])
        annwer = "YES"
        break
      }
    }
    // ここにNOで来た時点でアウトなので終わり
    if annwer == "NO" {
      break
    }
  }
  fmt.Println(annwer)
}

func getReverse(s string) string {
  rs := []rune(s) // 今回マルチバイト文字ではないが想定してrune
  for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
    rs[i], rs[j] = rs[j], rs[i]
  }
  return string(rs)
}

コード長:1263 Byte
実行時間:174 ms
メモリ:3912 KB

##その他1(追記)
コメントでアドバイスいただいた正規表現にて実現した場合、とてもスッキリしています。
アルゴリズム理解のため、パッケージはあまり使いたくない気持ちでAtCorderをやっていますが、このスッキリ感には負ける…。

package main
 
import (
  "fmt"
  "regexp"
)
 
func main() {
  var s string
  divide := `^(dream|dreamer|erase|eraser)*$`
  
  fmt.Scanf("%s", &s)
 
  if regexp.MustCompile(divide).Match([]byte(s)) {
    fmt.Println("YES")
  } else {
    fmt.Println("NO")
  }
}

コード長:279 Byte
実行時間: 164 ms
メモリ:2820 KB

##その他2
stringsパッケージのReplaceで一致したら""と置換してしまい、最後0文字になったらYESという方法
※AtCorderの白昼夢で検索するとよくヒットしますので割愛。

##おわりに
提出コードを書いたときは、冗長すぎておかしくなりそうでした。
正規表現のアドバイスをくださった@superrino130さん、ありがとうございました!!
以下は引き続き捜索中です。あまりニッチではないパッケージで実現可能でしたら教えていただけると嬉しいです。

  • 文字列のリバース
  • 開始〜終了桁数を指定した文字列の抜き出し(例:abcを1文字目から2文字目で抜き出して「b」を求める)
1
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?