[Leetcode][C++][난이도 Easy] Roman to Integer

Leetcode의 난이도 easy로 3번째 문제는 Roman to Integer입니다. 말 그대로, string 변수로 저장된 로마 숫자 기호들을 integer로 변환하는 문제인데요, 규칙을 파악하면 쉽게 해결할 수 있는 문제였습니다. 우선 문제 분석을 하고, 문제 해결을 위한 C++ 코드, 솔루션 코드 중 제일 많은 추천을 받은 코드를 순차적으로 살펴보겠습니다. 

 

Roman to Integer 문제 분석

 

[사진 1] Leetcode Roman to Integer 문제

 

문제의 핵심은 로마 기호 I, X, C가 주어진 로마 숫자 기호 string에서 어디에 위치하는지에 따라 다른 integer를 반환한다는 것입니다. 예를 들어, XI 는 11 인데요, IX 는 9입니다. 위 <사진 1>과 같이, 주어진 지문에서도 I, X, C 문자의 위치에 대한 예제를 제시하고 있군요. 

 

 

Roman to Integer 문제 해결을 위한 C++ 코드

 

class Solution {
public:
    int romanToInt(string s) {
        int roman_len = int(s.length());
        int result = 0;
        
        for (int i = 0; i < roman_len; i++) 
        {
            switch (s[i])
            {
                case 'I':
                    result += 1;
                    break;
                case 'V':
                    result += 5;
                    break;
                case 'X':
                    result += 10;
                    break;
                case 'L':
                    result += 50;
                    break;
                case 'C':
                    result += 100;
                    break;
                case 'D':
                    result += 500;
                    break;
                case 'M':
                    result += 1000;
                    break;
            }
        }
        
        if (roman_len == 1)
            return result;
        else if (roman_len > 1)
        {
            for (int i = 1; i < roman_len; i++)
            {
                if ((s[i] == 'V' || s[i] == 'X') && (s[i - 1] == 'I'))
                {
                    result -= 2;
                }
                else if ((s[i] == 'L' || s[i] == 'C') && (s[i - 1] == 'X'))
                {
                    result -= 20;
                }
                else if ((s[i] == 'D' || s[i] == 'M') && (s[i - 1] == 'C'))
                {
                    result -= 200;
                }
            }
        }
        
        return result;
    }
};

 

저는 이 문제를 해결하기 위해, 먼저 string s에 저장되어 있는 모든 로마 문자를 integer로 변환해서 덧셈 연산을 수행했습니다. 이를 위해, 현재 입력받은 string s의 길이를 roman_len 이라는 int 변수에 저장해줬고, 최종 integer 값 결과를 result라는 int 변수로 반환하려고 합니다. 바로 아래 for loop을 roman_len 만큼 실행하는데요, 각 로마 문자에 대응되는 case 문이 있다면, result에 각 로마 문자가 의미하는 integer 값을 누적해서 더했습니다. 즉, result = result + 1 처럼, result 값을 계속 갱신시킵니다. 

 

for loop을 전부 돌았다면, 한 번 roman_len의 길이를 검사해서 만약 1이라면, result에는 1만 저장되어 있으니까 바로 반환합니다. 그런데 roman_len의 길이가 1이 아니라면, 2개 이상의 로마 문자가 존재한다는 의미이므로, 이를 처리하는 for loop을 다시 수행합니다. 이때 제가 해결하려는 요소가 I, X, C 문자의 위치에 따라 숫자가 바뀐다는 사항이었습니다. for loop을 1번째 인덱스부터 시작해서, 현재 i 번째 인덱스가 V 또는 X이고, (i - 1)번째 인덱스가 I 라면, 지금까지 합산해서 얻은 result에서 2를 빼면 끝납니다. 한 번 예제를 들어서 설명해보겠습니다. 만약 IV 가 입력이라면, result는 1 + 5  = 6 입니다. 그런데 여기서 2를 빼면 4가 됩니다. 결국, 처음부터 I, X, C 문자의 위치까지 고려해서 최종 결과를 도출할 필요가 없는거죠. 우선 전체 integer 합을 구한 다음, I, X, C의 위치에 따라, 2, 20, 200을 그때 그때 마다 빼주면 됩니다. 

 

 

Roman to Integer 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

class Solution {
public:
    int romanToInt(string s) {
        int ans=0;
        unordered_map <char,int> mp{
        {'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};

    for(int i=0;i<s.size();i++){
        if(mp[s[i]]<mp[s[i+1]]){
            //for cases such as IV,CM, XL, etc...
            ans=ans-mp[s[i]];
        }
        else{
            ans=ans+mp[s[i]];
        }
    }
        return ans;
    }
};

 

다른 분이 짰던 코드도 살펴보겠습니다. 이 코드에서는 각 로마 숫자 문자에 대응되는 아라비아 숫자의 관계를 unordered map으로 하드 코딩 해두었습니다. 이후 total을 1000으로 초기화 시킨 다음, (주어진 로마 문자열의 길이 - 2) 부터 0이 될 때까지 int 변수 i 에 대해 for loop을 수행합니다. 저의 풀이와 반대로 for loop을 동작시켰군요. 이후 if 문을 통해서, 현재 인덱스 i 보다 앞에 위치한 인덱스 하고의 비교를 수행하는데요, 저처럼 각 로마 문자마다 하나씩 확인하는 방법이 아니라서, 더 효율적인 코드라고 생각됩니다 (역시 제가 짠 코드보다 다른 사람이 짠 코드가 대단하다고 느껴집니다 ㅠㅠ). if 문의 작동 방식과 관련해서, 다시 예제로 설명 하겠습니다. 만약 IV 라는 문자열이 들어왔다면, 1 < 5 이므로, total에서 1을 뺍니다. 만약 VI 라면, total에서 1을 더하겠죠.

 

 

지금까지 leetcode easy 난이도 문제 중 하나였던 Roman to Integer 문제를 살펴보았습니다. 다음 문제도 이어서 포스팅 올리겠습니다!