📘

leetcode"Roman to Integer"をGoで解いてみた

2022/08/21に公開

LeetCode

tech

概要

leetcodeのEasy問題の一つ、"Roman to Integer"をGoで解いていく。

解答のプロセス

以下のように問題を解いていくことを考えた。

上記を参考に解答を作成する。

(1)ローマ数字をアラビア数字に変換するためのハッシュテーブルの作成

使用されるローマ数字は、

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

である。これらを下記のようにmap関数を用いて整理する。

roman_numbers := map[string]int{"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

(2)ローマ数字をアラビア数字に変換する

ローマ数字からアラビア数字への変換の際に肝となるのは、ⅣやⅨのような数字の存在である。
解答のプロセスに記載したようにLXIIIのような数字であれば、先頭から一つ一つのローマ数字を総和することで答えを導ける。
では、XIVはどうだろうか。この場合、正解は14であるが、先頭から一つ一つ足していくと、16となってしまう。そこでローマ数字の先頭から各数字を確認し、その数字が一つ前の数字より大きくなる場合かそうでないかで場合分けを行うのが良い。
例えば、XIVの場合、
X = 10　は先頭の数字なのでそのまま足す。
I = 1 　はXよりも小さい数字なのでそのまま足す。
V = 5 　はIより大きくなるため、直前で足したIは-1として足すべきだとわかる。なので、-1×2+5を足す。
これにより、XIV = 14を導くことができる。

作成したコード

package main

import "fmt"

func romanToInt(s string) int {
	roman_numbers := map[string]int{"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
	//fmt.Println(roman_numbers)
	if s == "" {
		return 0
	}
	num, past_num, sum := 0, 1001, 0
	for i := 0; i < len(s); i++ {
		char := s[i : i+1]
		fmt.Println(char)
		num = roman_numbers[char]
		if num <= past_num {
			sum = sum + num
		} else {
			sum = sum + num - 2*past_num
		}
		past_num = num
	}
	return sum
}

func main() {
	fmt.Println(romanToInt("LVIII"))
	//fmt.Println(romanToInt("MCMXCIV"))
}

参考

よりスマートな方法として、下記が参考になる。

感想

ポイントとしては、

ローマ数字をアラビア数字に変換するためのハッシュテーブルの作成
ローマ数字特有の数値表現を場合分けによりアルゴリズムに落とす

概要

解答のプロセス

(1)ローマ数字をアラビア数字に変換するためのハッシュテーブルの作成

(2)ローマ数字をアラビア数字に変換する

作成したコード

参考

感想

Discussion