Intuition

로마 숫자 종류가 7개로 한정되어 있고, 기본 규칙은 무조건 큰 숫자에서 작은 숫자의 흐름인데,
그것에 반할 때에만 특수하게 처리하므로 숫자 7개를 따로 dictionary처럼 사용하면서 문제를 풀면 되겠다고 생각했다.

Approach

우선 숫자 7개를 dictionary처럼 쓸 수 있도록 함수를 만들어줬다.

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

일반적인 경우에는 그냥 해당 알파벳만큼 더하면 된다.

int res=0;
    for (int i=0;s[i]!=0;i++){
        int num=dict(s[i]);
        res+=num;
    }

그러나, 작은 숫자 다음에 큰숫자가 나올 때에는 처리하는 방식이 다르다.
예를 들어, $CM=1000-100=M-C$로 처리해야한다.
그런데 위까지의 과정에서 내가 이미 값을 더해버린 상태 즉, $C+M$까지 계산해놓은 상태다.
여기서 $C+M$을 $M-C$로 되돌리려면 원래 계산결과$C+M$에서$-2\times C$를 하면 된다.
그리고 이렇게 현재 숫자가 이전 숫자보다 큰지 작은지 알기 위해서, 이전숫자를 저장하는 변수 $pre$를 활용해줬다.

int pre=1000, res=0;
    for (int i=0;s[i]!=0;i++){
        int num=dict(s[i]);
        res+=num;
        if (pre<num){
            res-=2*pre;
        }
        pre=num;
    }

Solution

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

int romanToInt(char * s){
    int pre=1000, res=0;
    for (int i=0;s[i]!=0;i++){
        int num=dict(s[i]);
        res+=num;
        if (pre<num){
            res-=2*pre;
        }
        pre=num;
    }
    return res;
}

Complexity

• Time Complexity : $O(n)$
• Space Complexity : $O(n)$

교수님 풀이

내가 이전 배열의 것을 확인하여 특수 케이스를 처리한 것과 달리, 교수님은 다음 배열을 미리 확인하여 처리하셨다. 이렇게 하면 상대적으로 간단하게 계산을 할 수 있는 것 같다. (큰 차이는 없다.)

지적 및 질문 환영합니다.