[LeetCode] 13. Roman to Integer (C++)

Problem Overview

Roman to Integer - LeetCode

 

 

이번에 풀 문제는 Roman to Integer로, 7개의 Symbol로 표현되는 로마 숫자를 Integer로 변경하는 코드이다. 

난이도는 'Easy'이다.  

문제에서 까다로운 점을 굳이 뽑자면, 왼쪽에 작은 숫자가 있을 경우에는 빼줘야하며 (IV = 4) 오른쪽에 작은 숫자가 있을 경우에는 더해줘야 한다.(VI=6) 

문제는 간단하기에 이쯤하고, 바로 문제를 풀어보도록 하자.

Approach

문제에서는 Symbol과 대응되는 Value를 주어줬으니, 문제를 읽고 가장 먼저 생각이 든 것은, 문자열을 하나씩 읽으면서 각 문자에 해당하는 값을 매칭시키는 것이었다. 

로마자 문자와 정수 값을 쌍으로 연결하기 위해 Switch문과 Hash map(Unordered map) 중 어떤 것을 사용할까 고민하다가 코드 가독성 측면이나 효율성 측면에서 Hash map이 더 낫다고 생각이 들어 Hash map을 사용하기로 했다.

Hash map에 대해 간략하게 설명을 하자면,

Hash map은 데이터를 Key와 Value의 쌍으로 저장하는 도구이다. 간단한 예시로, 사전을 들 수 있겠다. 우리가 사전에서 'Apple'이라는 단어의 의미를 찾기 위해서 사전의 첫 페이지를 모두 읽는 것보단, 'A'로 시작하는 부분을 펼쳐서 단어를 찾아낼 것이다. Hash map도 이와 비슷하다고 생각하면 된다.

이러한 Hash map이 효율적인 이유는 데이터 검색, 삽입, 삭제에 걸리는 시간 복잡도가 O(1) 에 수렴하기 때문이다. 즉, 데이터가 10개든 100개든 상관없이 찾는 속도가 거의 일정하다고 볼 수 있다.

큰 흐름은 다음과 같이 생각했다.

1. Hash map 선언 및 초기화
2. 결과값 담을 변수 선언 및 초기화(total=0)
3. 문자열 탐색 및 Integer 변환
4. 결과값 반환

 

이때 주의할 점이, 3번 과정이다. IV의 경우 4가 되고, VI의 경우 6이 되어야 한다. 

기본적으로 문자열 탐색은 왼쪽부터 오른쪽으로 읽어오기 때문에, "현재 문자의 값"과 "그 다음 문자의 값"을 비교하여서, 만약 다음 idx의 문자의 Value가 더 크다면 현재 값을 빼주고, 작거나 같다면 그대로 더해주면 된다.

즉, Pseudocode를 적어보자면, 다음과 같다.

1. 로마자 문자를 정수 값으로 매핑해둘 Hash map을 초기화
2. 최종 결과값을 저장할 변수 total을 0으로 초기화
3. 입력된 문자열 s의 처음부터 끝까지 반복문을 돈다.(for(int i=0...))
	a. 현재 문자 s[i]의 정수값을 가져온다.
    b. if s[i]가 마지막 문자가 아니고, s[i]보다 s[i+1]가 더 크다면 : 
    	- total에서 현재 문자의 값을 뺀다.
    c. else (현재 값이 다음 값보다 크거나 같거나, 마지막 문자라면) :
    	- total에 현재 문자의 값을 더한다.
4. 반복문이 끝나면 total을 반환한다.

 

Code

#include <unordered_map>

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

        int total = 0; 

        for(int i=0; i<s.size(); ++i){
            if((i != s.size()-1) && (roman[s[i]] < roman[s[i+1]])){
                total -= roman[s[i]];
            }
            else total += roman[s[i]];
        }

        return total;
    }
};

 

Complexity Analysis

시간 복잡도의 경우(Time Complexity) 문자열 s의 길이 N만큼 한 번의 반복문을 순회하므로, O(N)이 되겠다.(Hash map 검색 시간은 O(1))

공간 복잡도의 경우(Space Complexity) unordered_map에 저장된 로마자 기호는 항상 7개로 고정되어 있으므로, 입력 크기 N에 상관없이 일정한 메모리만 사용한다. 즉, O(1)

Review

처음에는 그냥 순서대로 더하면되지 않나? 라고 생각했지만, 앞뒤 문자의 크기를 비교해야 한다는 점을 문제를 잘 읽어보니 알았다. 역시 문제에 대해 정확히 이해하는 능력도 참 중요한 것 같다. 이렇게 쉬운 문제인데,,,, 열심히 연습해보자.