Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000For example, 2 is written as II in Roman numeral, just two one's 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.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
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].
처음에 제일 단순하게 풀어본 deque와 if로 풀기.
아니 근데 마지막 숫자는 꼭 한번 더 append해서 에러남. 왜? append하는고야??
from collections import deque
class Solution:
def romanToInt(self, s: str) -> int:
dic = {"M":1000, "D": 500, "C": 100,"L":50, "X":10, "V": 5, "I":1}
#로마숫자는 7개의 대표 심볼로 표현할 수 있으며, 다음과 같은 값을 가짐.
# XL, XC 가능. IV, IX 가능. CD, CM 가능
calc = 0
deq = deque()
for i in s:
deq.append(i)
while len(deq)>1:
romanNum = deq.popleft()
nextNum = deq[0]
if romanNum == "M" :
calc += 1000
if romanNum == "D" :
calc += 500
if romanNum == "C" :
if nextNum == "D" :
calc += 400
deq.popleft()
if nextNum == "M" :
calc += 900
deq.popleft()
else :
calc += 100
if romanNum == "L" :
calc += 50
if romanNum =="X" :
if nextNum == "L" :
calc += 40
deq.popleft()
if nextNum == "C" :
calc += 90
deq.popleft()
else :
calc += 100
if romanNum =="V" :
calc += 5
if romanNum == "I" :
if nextNum == "V" :
calc += 4
deq.popleft()
if nextNum == "X" :
calc += 9
deq.popleft()
print(deq,calc)
else :
calc += 1
print(deq, calc)
print(deq,calc)
if len(deq) > 0:
calc += dic[deq.popleft()]
return calc
그래서 다시 대소비교로 푼 풀이:
class Solution:
def romanToInt(self, s: str) -> int:
#로마숫자는 7개의 대표 심볼로 표현할 수 있으며, 다음과 같은 값을 가짐.
# 내림차순으로 +진행되는 숫자, 오름차순인경우는 -
dic = {"M":1000, "D": 500, "C": 100,"L":50, "X":10, "V": 5, "I":1}
calc = 0
cnt = len(s) - 1
for i in range(cnt):
j = i+1
thisNum = dic[s[i]]
nextNum = dic[s[j]]
if thisNum >= nextNum :
calc += thisNum
else :
calc -= thisNum
calc += dic[s[cnt]]
return calc