[C++] LeetCode - Roman to Integer (Map)

LeetCode의 1위부터 100위까지 순서대로 하려고 했는데, 생각보다 난이도가 어려운 문제는 시간이 너무 오래 걸려서... 연습차원에서 EASY 등급부터 모두 끝내기로 했습니다. 어려운 문제는 아닌데, C++을 하면서 char, string 등을 구분해야하는 트뤼키한 부분이 있었습니다.

---

문제 정의

---

---

로만 문제를 정수로 변환하는데 규칙이 있습니다. 보통은 큰 숫자가 앞에 나올 수 있는데, 6가지 케이스에 대해서는 작은 숫자가 먼저 나올 수 있다고하네요.

접근 방법

• 문제를 두번 풀었습니다. 처음에는 for문을 통해 첫 글자와 다음 글자를 비교하고, 6가지 케이스에 해당하면 각각 값을 더하는 식으로 했습니다.
• 아래 코드를 보시면 아시겠지만 좀 더러운 코드 같다는 느낌이 들고, 하위 5%의 속도로 결과를 맞출 수 있었습니다.
• c++에서 string을 for loop 을 돌려서 글자 하나씩 추출하게 되면 자료형이 char가 됩니다. 따라서 strcmp나 string형 기반으로 문자를 비교하면 안되고, map을 쓰더라도 자료형이 char여야 합니다. string으로 쓸 경우 아래와 같이 char to string 변환이 가능합니다.
• string temp; temp += character;
• 두번째 접근 방법은, 앞에 나온 숫자가 뒷자리보다 클 경우만 놓고 따지는 겁니다. 6가지 케이스를 모두 고려할 필요 없이, 일단 앞자리가 작으면 앞자리 숫자만큼 빼주기만 하면 되는 식입니다. 훨씬 간결한 방법입니다.
• 시간 복잡도는 O(n)인 것으로 보입니다. 문자열에 대해 한번만 for loop 을 돌렸고, 해쉬맵의 경우 값을 찾는 것은 O(1)에 해당합니다.

---

코드

---

처음 시도한 방법

---

class Solution {
public:
    int romanToInt(string s) {
        int answer = 0;
        unordered_map<string, int> m;
        
        m["I"] = 1;
        m["V"] = 5;
        m["X"] = 10;
        m["L"] = 50;
        m["C"] = 100;
        m["D"] = 500;
        m["M"] = 1000;
        
        
        for (int i=0; i<s.size(); i++) {
            // s[i] is char! not string.
            
            string temp;
            string temp2;
            temp += s[i];
            temp2 += s[i+1];
            
            if (i != s.size()-1) {
                if (temp =="I" && temp2 == "V") {
                    i=i+1;
                     answer += 4;
                } else if (temp =="I" && temp2 == "X") {
                    i=i+1;
                    answer += 9;
                } else if (temp =="X" && temp2 == "L") {
                    i=i+1;
                    answer += 40;
                } else if (temp =="X" && temp2 == "C") {
                    i=i+1;
                    answer += 90;
                } else if (temp =="C" && temp2 == "D") {
                    i=i+1;
                    answer += 400;
                } else if (temp =="C" && temp2 == "M") {
                    i=i+1;
                    answer += 900;
                } else {
                    answer += m[temp];
                }
            } else {
                string temp3;
                temp3 += s[i];
                answer += m[temp3];
            }
            
            
                
        }
        
        
        
        return answer;
    }
};

---

두번째로 시도한 방법

---

class Solution {
public:
    int romanToInt(string s) {
        int answer = 0;
        unordered_map<char, int> m;
        
        m['I'] = 1;
        m['V'] = 5;
        m['X'] = 10;
        m['L'] = 50;
        m['C'] = 100;
        m['D'] = 500;
        m['M'] = 1000;
        
        
        for (int i=0; i<s.size()-1; i++) {
            if (m[s[i]] >= m[s[i+1]]) {
                answer += m[s[i]];
            } else {
                answer -= m[s[i]];
                
            }
            
        }
        
        answer += m[s[s.size()-1]];
        
        return answer;
    }
};

---