LeetCode - roman to integer

roman to integer

• Difficulty : easy
• 😂 반대가 더 많은 알고리즘 문제이며, 난이도 중급정도 되는거같은데..흠;

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.

• 로마숫자표기법을 정수로 변환하면 된다.
• III => 3, IV => 4

example
Example 1:
Input: "III"
Output: 3

Example 2:
Input: "IV"
Output: 4

Example 3:
Input: "IX"
Output: 9

Example 4:
Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

• 이 알고리즘 핵심은 로마숫자표기법을 잘 살펴보면 V X C M 등에 뒤에 숫자가 있으면 빼줘야한다.

solution

• 작성 언어 : javascript

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

};

• leet code runtime 148 ms

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

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


  let sum = 0;
  let tempBeforeRomanValue = '';
  let addValue = 0;

  [...s].forEach((char, index) => {

    const nextValueSymbol = s[index + 1];

    if (index === 0) {
      if (ROMAN_SYMBOL[char]) {
        if (ROMAN_SYMBOL[char] < ROMAN_SYMBOL[nextValueSymbol]) {
          tempBeforeRomanValue = ROMAN_SYMBOL[char];
        } else {
          sum += ROMAN_SYMBOL[char];
          tempBeforeRomanValue = ROMAN_SYMBOL[char];
        }
      }
    } else {
      if (ROMAN_SYMBOL[char]) {
        if (tempBeforeRomanValue < ROMAN_SYMBOL[char]) {
          addValue += Math.abs(tempBeforeRomanValue - ROMAN_SYMBOL[char]);
          tempBeforeRomanValue = ROMAN_SYMBOL[char];
        } else {

          if (ROMAN_SYMBOL[char] < ROMAN_SYMBOL[nextValueSymbol]) {
            tempBeforeRomanValue = ROMAN_SYMBOL[char];
          } else {
            sum += ROMAN_SYMBOL[char];
            tempBeforeRomanValue = ROMAN_SYMBOL[char];
          }

        }


      }
    }

  });

  return sum + addValue;

};

• "MCMXCIV" 이 로마숫자표기법을 숫자로 전환하면 이렇다 -> 1000 100 1000 10 100 1 5
• 로마숫자표기법을 살펴보면 VIII 같은 경우 앞에 숫자가 크거나 같으면 더해나가면 된다.
• "MCMXCIV" => 1000 + (100 - 1000) 이렇게 되어야하는데, 다음 심볼값이 큰 경우는 저 연산만 따로 처리해주는 부분을 구현했다.

• 개선 코드😎

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

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


  let sum = 0;
        
    for(let index = 0; index < s.length; index++) {
        
      const currentSymbol = s[index];
      const nextSymbol = s[index+1];
     
        if(ROMAN_SYMBOL[currentSymbol] < ROMAN_SYMBOL[nextSymbol]) {
            sum += ROMAN_SYMBOL[nextSymbol] - ROMAN_SYMBOL[currentSymbol];
            index++;
        } else {
            sum += ROMAN_SYMBOL[currentSymbol];
        }
    }

  return sum;

};

• 결론적으로 다음에 나오는 로마숫자표기법이 크면 IV 하나로 간주해서 연산을 해주고 index 를 건너뛰게 해주면 된다.
• 실행시간은 140 ms 가 나오는데;; 아니 이런 비슷한 코드 누구는 100 ms 밑으로 나오는데 이유가 무엇인가 ㅠㅠ
• 다른 풀이를 보니, 거꾸로 연산을 하는것도 있다.(계산해보니 쌉가능)