[leetCode] 13. Roman to Integer (Easy) 풀이

❓ 문제

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

로마 숫자는 7개의 다른 기호로 표시됩니다.: I, V, X, L, C, D 그리고 '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 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.

 

예를 들어, 2는 로마 숫자로 II로 표기되며 2개만 더하면 됩니다. 12는 단순히 X + II인 XII로 작성됩니다. 숫자 27은 XXVII인 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:

 

로마 숫자는 일반적으로 왼쪽에서 오른쪽으로 큰 것에서 작은 것 순으로 표기합니다. 그러나 4에 대한 숫자는IIII가 아닙니다. 대신 숫자 4는 IV로 표기됩니다. 1은 5보다 앞에 있기 때문에 빼서 4가 됩니다. 같은 원칙이 IX로 쓰여진 숫자 9에도 적용됩니다. 빼기가 사용되는 6가지 경우가 있습니다.

• 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.
• V(5)와 X(10) 앞에 I를 놓아 4와 9를 만들 수 있습니다.
• X는 L(50)과 C(100) 앞에 위치하여 40과 90을 만들 수 있습니다.
• C는 D(500)와 M(1000) 앞에 위치하여 400과 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].

❗ 내 답변

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const strArr = s.split('');
    const numArr = strArr.map(s => {
        switch(s) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
        }
    })

    let sum = numArr[numArr.length - 1];
    for (let i = numArr.length - 1; i >= 0; i--) {
        if (i-1 < 0) {
            break;
        }

        if (sum > numArr[i-1] && numArr[i] > numArr[i-1]) {
            sum -= numArr[i-1];
        } else {
          sum += numArr[i-1];
        }
    }

    return sum;
};

이거 Easy 맞나..?
난 좀 어려웠다. 여러번 Run 시키고 뜯어고쳐 성공할 수 있었다...

 

주어진 로마 숫자 String을 split 하여 배열에 나눠담고,
숫자로 변환시켜 배열에 담았다.

숫자 배열을 뒤에서부터 반복 돌면서, 합산시켜줬다.
현재 비교 숫자가 그 앞자리 보다 크고, (numArr[i] > numArr[i-1])
sum이 현재 비교 숫자의 앞자리보다 크다면 (sum > numArr[i-1])
sum에서 현재 비교 숫자보다 앞자리 값을 뺐다.

 

예를 들어, IX 같은 경우, 배열에 [1, 5] 가 담기게 될것 이고,
뒤에서 부터 비교 했을 때,
5(현재 비교 숫자) 1(현재 비교 숫자의 앞자리)보다 크고,
sum(5)이 1(현재 비교 숫자의 앞자리)보다 크기 때문에
sum(5)에서 현재 비교 숫자보다 앞자리 값(1)을 뺐다.
따라서 4가 나오게 된다.

이 외의 숫자들은 모두 sum에 현재 비교 숫자의 앞자리 값을 더해줬다.

 

예를 들어, III 같은 경우, [1, 1, 1]이 담기게 되고,
뒤에서 부터 비교 했을 때,
현재 비교 숫자가(1) 앞자리(1)보다 크지도 않고,
sum(1)이 현재 비교 숫자의 앞자리 값(1) 보다 크지 않기 때문에
sum(1)에 현재 비교 숫자의 앞자리 값(1)을 더 해준다.
이를 반복하면 3이 나오게 된다.

❗ Runtime이 가장 빨랐던 답변과 비교

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const symbols = new Map();
    symbols.set('I', 1);
    symbols.set('V', 5);
    symbols.set('X', 10);
    symbols.set('L', 50);
    symbols.set('C', 100);
    symbols.set('D', 500);
    symbols.set('M', 1000);
    const numerals = s.split('');
    let prev = symbols.get(numerals[0]);
    let sum = 0;
    for (let i = 0; i < numerals.length; i++) {
        const curr = symbols.get(numerals[i]);

        if (curr > prev) {
            const subtractedValue = curr - prev;
            sum -= prev;
            sum += subtractedValue;
        } else {
            sum += curr;
        }
        prev = curr;
    }
    return sum;
};

내 코드와 비교해봤을 때,
나는 반복을 돌면서 split 해 담은 로마 숫자 배열을 숫자 배열에 다시 담아줬지만,
이 답변은 new Map()을 사용하여 불필요한 반복을 줄였다.
split 해온 로마 숫자 배열을 반복하며 바로 symbols라는 Map에서 숫자 값을 매핑해 오는 것이다.

내 코드에서 로마 숫자 배열을 숫자 배열로 반복해 담는 과정을 new Map()으로 바꿔 다시 돌려봤더니,
116ms 로 시간이 단축되는 걸 확인할 수 있었다.
(RunTime 시간은 돌릴 때마다 달라져서 정확하진 않다.)

 

for 문 내에서 비교하는 과정에선,
나는 뒤에서 부터 앞으로 반복을 돌렸고,
이 답변은 앞에서부터 뒤로 반복을 돌렸다.

if 조건문에서 나는 sum 과 prev(현재 비교 숫자), cur(현재 비교 숫자의 앞 숫자) 를 모두 비교 했었는데,
이 답변을 보니 그럴 필요가 없었다.
cur이 prev 보다 큰 경우, sum = sum + (curr - prev) - prev 를 해주었다.
이말인 즉, IV 인 경우, [1, 5]가 되어 아래와 같은 과정을 거친다.

• 첫번 째 반복
  • cur: 1
  • prev: 1
  • cur > prev => false
  • sum += curr => sum = 1
• 두번 째 반복
  • cur : 5
  • prev: 1
  • cur > prev => true
  • sum = sum + (curr - prev) - prev => 1 + (5 - 1) - 1 => sum = 4

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(string) {

  const nums = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000
  }

  let acc = 0;

  for (let i = 0; i < string.length ; i += 1) {
    if (nums[string[i]] < nums[string[i + 1]]) {
      acc -= nums[string[i]];
    } else {
      acc += nums[string[i]];
    }
  }
  return acc;
};

Runtime이 가장 빨랐던 답변과 비교해보면,
이 답면은 new Map() 이 아니라 Object 를 활용했다.

개인적으로 for 문 내에서 비교 하는 과정이
내 답변과 Runtime이 가장 빨랐던 답변과 비교해 보았을 때
이 답변이 가장 가독성 좋고 깔끔한 것 같다.

 

이 답변 역시 나와 달리 배열 앞에서 뒤로 1씩 증가하며 반복을 돌렸다.
편의 상 nums[string[i]] 를 curr, nums[string[i+1]]을 next 라고 지칭하겠다.
curr < next 인 경우, acc, 즉 sum에서 curr을 빼고,
이 외의 경우 모두 sum 에 curr를 더했다.

예를 들어, IV 인 경우, [1, 5]가 되어 아래와 같은 과정을 거친다.

• 첫번 째 반복
  • curr: 1
  • next: 5
  • curr < next => true
  • acc -= curr => acc = -1
• 두번 째 반복
  • cur: 5
  • next: undefined
  • curr < next => false
  • acc += curr => -1 + 5 = 4

완전 깔끔하다.
어떻게 여러 케이스를 if 조건 하나로 요약하여 생각할 수 있는거지...
분발해야겠다.

💡 개선 방안

반복을 돌면서 로마 숫자(문자)를 숫자로 변환하지 말고
Map이나 Object를 활용하여 불필요한 반복을 줄인다.

비교 조건을 조금 더 가독성 있게 변경한다.(이 부분은 아직 많이 생각하고 노력해야할 것 같다. 바로 안 떠오르기 때문...)