목차
문제 개요
난이도 - EASY 사용 언어 - C++
지난 12번 문제와 유사한 문제로 이번에는 로마자 숫자에서 정수형 숫자로 변환하는 문제입니다.
문제 - LeetCode 13. Roman to Integer
풀이
Solution - 1
로마자 숫자를 정수로 바꾸는 방법은 매우 쉽게 유도가능합니다.
첫 번째로 각 로마자 심볼들은 정해진 값이 있습니다. 해당 값을 1:1로 매칭하기 위해서 std::map STL 자료형을 사용합니다.
두 번째로 4, 9와 같은 문자는 IV, IX와 같이 5, 10을 나타내는 심볼 앞에 1을 나타내는 심볼이 붙어서 나오게됩니다. 그리고 로마자 숫자를 살펴보면 4, 9와 같은 경우를 제외하고 작은 크기의 심볼이 큰 숫자보다 앞에 오는 경우가 없습니다.
예를 들어 LVIII라는 값은 58로 L은 50, V는 5, I는 1입니다. MCMXCIV은 1994로 M은 1000, CM은 900, XC는 90, IV는 4입니다.
이렇듯 4, 9를 제외한 모든 심볼은 항상 내림차순으로 표현됩니다. 이 점을 유의해서 코드를 작성합니다.
제출 결과
실행 속도는 12ms로 다른 C++ 제출자에 비해 60% 가량의 성능밖에 되지 않습니다.
추측하컨데 아마도 std::map STL 자료형을 사용하면서 메모리 생성 과정과 접근 과정에서 많은 시간을 소요하고 있다는 생각이 듭니다.
코드 전문
#include <string>
#include <map>
class Solution
{
public:
int romanToInt(std::string s)
{
int result = 0;
for (int i = 0; i < s.size(); i++)
{
result += symbols[s[i]];
if (i - 1 >= 0 && symbols[s[i]] > symbols[s[i - 1]])
{
result -= (symbols[s[i - 1]] * 2);
}
}
return result;
}
private:
std::map<char, int> symbols {
std::make_pair('I', 1), std::make_pair('V', 5),
std::make_pair('X', 10), std::make_pair('L', 50),
std::make_pair('C', 100), std::make_pair('D', 500),
std::make_pair('M', 1000)
};
};Solution - 2
방법 1은 std::map을 이용해 로마자 숫자를 정수형으로 변환했지만, 해당 부분을 삭제하고 switch문 하드 코딩으로 바꿔서 실행해보겠습니다.
제출 결과
실행 속도는 4ms로 기존의 12ms보다 향상됨을 확인할 수 있습니다.
기존의 std::map을 이용한 메모리 접근 대신 switch문을 이용해 하드 코딩으로 실행하여 기존에 비해 높은 실행 속도를 얻을 수 있었습니다.
코드 전문
#include <string>
#include <map>
class Solution
{
public:
int romanToInt(std::string s)
{
int result = 0;
for (int i = 0; i < s.size(); i++)
{
switch(s[i])
{
case 'M':
result += 1000;
break;
case 'D':
result += 500;
break;
case 'C':
if ((s[i+1] == 'D') || (s[i+1] == 'M')) result -= 100;
else result += 100;
break;
case 'L':
result += 50;
break;
case 'X':
if ((s[i+1] == 'L') || (s[i+1] == 'C')) result -= 10;
else result += 10;
break;
case 'V':
result += 5;
break;
case 'I':
if ((s[i+1] == 'V') || (s[i+1] == 'X')) result -= 1;
else result += 1;
break;
}
}
return result;
}
};
