Roman to Integer

Algorithm
algorithm, leetcode

leetcode 문제링크

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, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number > twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

나의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 143 - 152ms
var romanToInt = function(s) {
  const ROMAN = {
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000
  }
  const newS = s.split('').map(item => ROMAN[item]);
  return newS.reduce((acc, item, idx, arr) => {
    const before = arr[idx - 1];
    return acc + (before < item && before ? item - (before * 2) : item)
  }, 0)
};

다른 방법도 생각해보려고 했는데, 도저히… map(), reduce() 메소드로 배열을 두번 탐색한게 마음에 걸린다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 156ms
var romanToInt = function(s) {
  const ROMAN = {
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000
  }
  return s.split('').reduce((acc, item, idx, arr) => {
    const before = arr[idx - 1];
    const beforeInt = ROMAN[before]
    const itemInt = ROMAN[item]
    return acc + (beforeInt < itemInt && beforeInt ? itemInt - (beforeInt * 2) : itemInt)
  }, 0)
}

reduce 한번으로 처리하도록 변경했는데 이것도 그닥 속도가 개선되지는 않았다.

다른 사람 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let getIntFromRoman = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000
};

var romanToInt = function(s) {
    let sum = 0;
    let curr, next;
    for(let i = 0; i < s.length-1; i++) {
        curr = getIntFromRoman[s[i]];
        next = getIntFromRoman[s[i+1]];
        if(curr < next)
            sum -= curr;
        else
            sum += curr;
    }
    return sum + getIntFromRoman[s[s.length-1]];
};

for문을 통해 따로 sum 에 더해주는 방식으로 처리했다. 그리고 현재 문자가 다음 문자보다 작으면 오히려 빼주는데, 그렇게 하면 4내지는 9가 나오게 되니 이렇게 풀 수도 있구나하고 깨달음이…

나는 조건 분기했는데…

Share Comments