[LeetCode] 13. Roman to Integer

Problem

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 + 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].

Solution

Logic

• Roman 숫자에 해당하는 문자열 s를 앞에서 부터 한 문자씩 읽어들여 각 Roman 숫자에 해당하는 정수로 변환하면 문제를 해결할 수 있을 것으로 보이나, 다음과 같은 예외 사항들이 존재한다

  "IV" -> 4 not 6
  "IX" -> 9 not 11
  "XL" -> 40 not 60
  "XC" -> 90 not 110
  "CD" -> 400 not 600
  "CM" -> 900 not 1100
  

• 그리고 다음과 같이 변환될 정수의 각 자리를 Roman 숫자로 표현하기 때문에 찾을 수 있는 규칙이 있다. ```java 1994 = “M” (1000) + “CM” (900) + “XC” (90) + “IV” (4)

Roman 숫자 안에서 4 혹은 9에 해당하는 “IV” 또는 “IX”가 한 번 등장 가능 40 혹은 90에 해당하는 “XL” 또는 “XC”가 한 번 등장 가능 400 혹은 900에 해당하는 “CD” 또는 “CM”이 한 번 등장 가능

- 따라서 Roman 숫자에 해당하는 문자열 s의 앞에서 부터 참조하여 정수로 변환하고 4또는 9가 들어가는 예외 사항을 처리하면 문제를 해결할 수 있다.
## **Code**
```java
class Solution {
    public int romanToInt(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'I' : res += 1;
                    break;
                case 'V' : res += 5;
                    break;
                case 'X' : res += 10;
                    break;
                case 'L' : res += 50;
                    break;
                case 'C' : res += 100;
                    break;
                case 'D' : res += 500;
                    break;
                case 'M' : res += 1000;
                    break;
            }
        }
        if (s.contains("IV") || s.contains("IX")) res -= 2;
        if (s.contains("XL") || s.contains("XC")) res -= 20;
        if (s.contains("CD") || s.contains("CM")) res -= 200;
        return res;
    }
}

Time Complexity

• 문자열 s의 길이를 n이라고 할때, 아래의 반복문에서 O(n)의 시간이 소요된다.

  for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'I' : res += 1;
                    break;
                case 'V' : res += 5;
                    break;
                case 'X' : res += 10;
                    break;
                case 'L' : res += 50;
                    break;
                case 'C' : res += 100;
                    break;
                case 'D' : res += 500;
                    break;
                case 'M' : res += 1000;
                    break;
            }
        }
  

• 그리고 아래의 조건문에서 상수 시간이 소요된다. 따라서 본 솔루션의 시간 복잡도는 O(n)이 된다.

  if (s.contains("IV") || s.contains("IX")) res -= 2;
  if (s.contains("XL") || s.contains("XC")) res -= 20;
  if (s.contains("CD") || s.contains("CM")) res -= 200;
  

  Solution2

  Logic

• Roman 숫자가 다음과 같은 예외 사항을 가진다.

  "IV" -> 4 not 6
  "IX" -> 9 not 11
  "XL" -> 40 not 60
  "XC" -> 90 not 110
  "CD" -> 400 not 600
  "CM" -> 900 not 1100
  

• 위의 예외 사항들을 예외가 아닌 상태로 만들면 다음과 같다.

  "IV" -> "IIII"
  "IX" -> "VIIII"
  "XL" -> "XXXX"
  "XC" -> "LXXXX"
  "CD" -> "CCCC"
  "CM" -> "DCCCC"
  

• 위를 고려하여 문자열 s를 변경하여 문제를 해결할 수 있다.

  Code

  class Solution {
    public int romanToInt(String s) {
        s = s.replace("IV", "IIII")
            .replace("IX", "VIIII")
            .replace("XL", "XXXX")
            .replace("XC", "LXXXX")
            .replace("CD", "CCCC")
            .replace("CM", "DCCCC");
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'I' : res += 1;
                    break;
                case 'V' : res += 5;
                    break;
                case 'X' : res += 10;
                    break;
                case 'L' : res += 50;
                    break;
                case 'C' : res += 100;
                    break;
                case 'D' : res += 500;
                    break;
                case 'M' : res += 1000;
                    break;
            }
        } return res;
    }
  }
  

  Time Complextity

• 아래의 문자열 변경 과정은 최소 0번 ~ 최대 3번의 계산, 즉 상수 시간이 소요된다.

  s = s.replace("IV", "IIII")
    .replace("IX", "VIIII")
    .replace("XL", "XXXX")
    .replace("XC", "LXXXX")
    .replace("CD", "CCCC")
    .replace("CM", "DCCCC");
  

• 문자열 s의 길이를 n이라 가정했을 떄, 위의 문자열 대치에 의해 문자열의 길이가 길어졌다 하더라도 n ~ n + 9번의 계산을 수행하게 된다. 따라서 본 솔루션은 O(n)의 시간복잡도를 가진다.

  int res = 0;
  for (int i = 0; i < s.length(); i++) {
    switch (s.charAt(i)) {
        case 'I' : res += 1;
            break;
        case 'V' : res += 5;
            break;
        case 'X' : res += 10;
            break;
        case 'L' : res += 50;
            break;
        case 'C' : res += 100;
            break;
        case 'D' : res += 500;
            break;
        case 'M' : res += 1000;
            break;
    }
  }