Description
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 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 + 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.
Intuition :
I have to consider that when the previous number is smaller than the current number , the previous number has to be substracted from the current number. but when the previous number is greater or equal to the current number the number has to be additional to the current number;
Approach :
1) store the values in the Hashmap with key-value pair.
2) Iterate the characters of string roman number string
3) check if the previous integer is smaller than the current integer.
4) when the previous value is smaller, simpley substract the number with the current value
Code :
class Solution {
public int romanToInt(String s) {
Map<Character,Integer> m = new HashMap<>();
m.put('I',1);
m.put('V',5);
m.put('X',10);
m.put('L',50);
m.put('C',100);
m.put('D',500);
m.put('M',1000);
int answer = 0;
for(int i=0; i<s.length(); i++){
if(i < s.length()-1 && m.get(s.charAt(i))<m.get(s.charAt(i+1))){
answer = answer - m.get(s.charAt(i));
} else{
answer = answer + m.get(s.charAt(i));
}
}
return answer;
}
}
Lets Say I have IV , It should return 4
The first I which is 1 will go to the if statement
answer = answer(0) - m.get(s.charAt(0) = -1
the next V which is 5 will go to the else statement
because i < s.length() - 1 prevents last element to be in if statement.
therefore
answer = -1 + 5
answer = 4
Performance
Time complexity of this algorithm is O(n) where n is the number of chars in the string
Space complexity of this algorithm is O(1) because this algorithm uses hashmap to store values of roman and integer .
since the size of the string input does not affect the hashmap, it is considered constant space.
(!!)
I think i have to solve this n times.. even this level is considered 'easy' i couldnt solve it but look other's solutions
'Programming > LeetCode' 카테고리의 다른 글
[Leetcode] #14. Longest Common Prefix (repeat : 0 ) (0) | 2024.01.31 |
---|---|
[LeetCode] #58. Length of Last Word (repeat : 0) (2) | 2024.01.23 |
[LeetCode] #169. Majority Element (repeat : 0 ) (0) | 2024.01.21 |
[LeetCode] #234 Palidrome LinkedList (repeat : 1) (0) | 2024.01.19 |
[LeetCode] #92. Reverse Linked List II (repeat : 0) (0) | 2024.01.18 |