0
1

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.

【LeetCode】就活に向けたコーディングテスト対策 #04

Last updated at Posted at 2021-06-13

#はじめに
こんばんは.
M1就活生がLeetCodeから,easy問題を中心にPythonを用いて解いていきます.

↓では,解いた問題のまとめを随時更新しています.
まとめ記事

#問題
今回解いたのは,難易度easyから 問題13のRoman to Integer です.
問題としては,文字列sで与えられるローマ数字を整数に直して値を出力するというもの.
ローマ数字は7種類の記号で表されており,それぞれ次の値となっています.

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

入力例と出力例は以下の通りです.

Example 1:

Input: s = "III"
Output: 3

Example 2:

Input: s = "IV"
Output: 4

Example 3:

Input: s = "IX"
Output: 9

Example 4:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

このとき,4を表す数字はIIIIではなくIV,9はIXとなっています.

#書いたコード
とりあえず,思いついたままに書いてみました.

class Solution:
    def romanToInt(self, s: str) -> int:
        dic = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        reverse_s = s[::-1]
        total, prev = 0, 0
        
        for i in reverse_s:
            if dic[i] >= prev:
                total += dic[i]
            else:
                total -= dic[i]
            prev = dic[i]
        
        return total

まず,それぞれローマ数字とその値に対応する辞書を用意します.ローマ数字は通常,左から順に大きい数字となるように書くルールがあるそうです(知らなかった).そのためまずは,ローマ数字を反転させて,末尾から順に加算していきます.このとき,4はIV,9はIXなどのルールがあるため,前の値と比較してそれ以上であれば現在の値を加算,そうでなければ減算することで引き算のルールに適用させました.

議論ページを見てみると,なるほどなと思うコードがありました.

class Solution:
    def romanToInt(self, s: str) -> int:
        translations = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        number = 0
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
        s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
        s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
        for char in s:
            number += translations[char]
        return number

ローマ数字の引き算を行うルールは全部で6通りらしいです.そのため,このコードのようにそれぞれのローマ数字を減算を使わない形に置換することで簡単に計算ができるみたいです(これはいい...).

#おわりに
Discussページでは,様々な言語での解き方を参照できるのでとてもおもしろいです.多角的な思考で問題を解けるようにこれからも頑張っていきたいですね.

今回書いたコードはGitHubにもあげておきます.

前回 次回

0
1
0

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
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?