[C] LeetCode 13. Roman to Integer

문제(원문)

 

문제(번역)

로마 숫자는 I,V,X,L,C,D,M으로 표현할 수 있다.

로마 숫자는 보통 큰 수부터 작은 수를 왼쪽에서 오른쪽으로 쓴다. 하지만, 4를 표현할 때는 IIII 대신 IV를 사용한다.

왜냐하면 4를 만들기 위해 5에서 1을 빼기 때문이다. 이러한 원칙은 9를 만들때도 사용된다.

로마 숫자가 주어졌을 때 이를 정수로 바꿔라.

접근 방법

처음엔 단순히 로마 숫자 심볼을 정수로 바꾸려고 시도했다. 당연히 실패했다.

보통은 큰 수부터 작은 수를 차례대로 쓰나, 일부 숫자를 만들기 위해는 작은수 큰수 순서대로 적힐 수 있다고 했다.

이를 활용하자.

 

문자열의 오른쪽에서 왼쪽으로 순회하면서, 기존 수보다 현재 수가 작으면 빼주는 형식으로 만들면 된다.

그게 아니고 기존 수보다 현재 수가 크면 더해주는 형태로 코드를 작성하면 된다.

 

이를 위해 문자를 정수로 바꾸는 함수도 추가로 만들었다.

 

소스 코드

int rti(char s) {
    if(s == 'I') return 1;
    else if(s == 'V') return 5;
    else if(s == 'X') return 10;
    else if(s == 'L') return 50;
    else if(s == 'C') return 100;
    else if(s == 'D') return 500;
    else return 1000;
}

int romanToInt(char* s) {
    int l = 0; while(s[l] != '\0') l++;
    char tmp= s[l-1];
    int  sum= rti(tmp);
    for(int i = l-2; i>=0; i--) {
        if(rti(s[i]) < rti(tmp)) {
            sum -= rti(s[i]);
        } else {
            tmp = s[i];
            sum += rti(tmp);
        }
    }
    return sum;
}

시간복잡도는 O(n) 이다. 추가적인 배열 선언도 없어서 공간복잡도 역시 O(1)이 될 것이다.