【LeetCode】13. Roman to Integer解答・解説【Python】

スポンサーリンク
この記事は約6分で読めます。

LeetCodeの問題を解きます。問題文は翻訳サイトと私の拙い英語力で和訳しており、正確でない可能性が高いためご注意ください。

スポンサーリンク

問題文

原文

Roman numerals are represented by seven different symbols: IVXLCD and M.

Symbol  Value

I      1

V     5

X     10

L     50

C     100

D     500

M     1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

 

Constraints:

  • 1 <= s.length <= 15
  • s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
  • It is guaranteed that s is a valid roman numeral in the range [1, 3999].

和訳

ローマ数字は7個の異なる記号で表されます。:I,V,X,L,C,D,M

記号と値の関係は以下の通り。

I: 1

V: 5

X: 10

L: 50

C: 100

D: 500

M: 1000

例えば、2はローマ数字ではⅡと書き、2つのⅠを組み合わせるだけです。12はⅫと書き、単純にⅩとⅡです。27はXXVⅡⅡと書き、XXとVとⅡを組み合わせています。

通常、ローマ数字は左から右に向かって大きい数から順に書きます。しかし、4はIIIIではありません。代わりにIVと書きます。1は5の前(左側)にあるので、5から1を引き算して4を作ります。同じ原理は9にも当てはまり、IXと書きます。引き算が使われる例は6つあります。

・IはVとXの前(左側)に置かれ、4と9を作ります。

・XはLとCの前(左側)に置かれ、40と90を作ります。

・CはDとMの前(左側)に置かれ、400と900を作ります。

ローマ数字が与えられるので、(アラビア)数字に変換してください。

 

制約

・与えられる文字列sの要素数は1~15

・sは('I', 'V', 'X', 'L', 'C', 'D', 'M')だけを含む

・sは!~3999までのローマ数字のみ

方針

・ローマ数字をアラビア数字に変化した後で、後ろ(右側)から足していきます。

・1つ前に足した数字を一時的な変数に保存し、次の数字が1つ前に足した数字よりも小さければ引き算します。

解答

コメント+コード

別解

こちらの方法だと、1つめの解答よりも早くなりました。

解答3:Python,英語コメント付き

2周目に突入しました。

解答の内容は1つ目と同じです。

英語面接に向けてまずはコメントを英語で記載できるようにしていきます。

自力で解答できるようになることは絶対ですが、解答の過程を英語で考えて説明できるようになることも必須です。

あと何周するとこれを満たせるのかわかりませんが、1つずつ積み上げていきたいと思います。

時間計算量は入力文字列sを一巡して走査するのでO(n)。

空間計算量は連想配列を使っているのでこれもO(n)でしょうか。

計算量の考え方はいまだに慣れません。正解しているかもよくわからないのですが、ちょくちょく調べながら考えていきたいと思います。

 

解答4:Python, 英語コメント

実際の面接の流れを意識して最初に英語で確認すべき内容を記載。

これをより内容を改善したうえで、緊張している中で口頭で説明できるようになる必要がある。

 

補足・参考・感想

聞いたことがあるものや知っていることでも、英語になると途端に何を指しているのかわからなくなるなと思うことがあります。今回のRoman numeralもそうでした。

LeetCodeに取り組むような人が目指す職場は、英語でのコミュニケーションもあるでしょうし、英語のドキュメントを読むことも多そうです。それぞれの専門分野に限って使われる言葉もあるでしょうし、単純にコードを書くだけでなく、エンジニアが自然と触れているものに自分もどんどん触れていきたいと思います。

LeetCodeでは、自分の提出物が他の提出者と比べて早いか、メモリをどれだけ消費したかが示されます。単に正解するだけでなく、より良い書き方がないかを考えたり調べたりするうえでとてもモチベーションになります。できれば、読みやすさや理解のしやすさも忘れずに実装できるようになりたいです。

 

 

次の記事:14. Longest Common Prefix

記事一覧:LeetCode記事一覧

 

コメント