Roman to Integer — 감산 규칙을 한 번의 스캔으로 처리하기

로마 숫자를 정수로 바꾸기, 어떤 문제인가요?

LeetCode 13번 문제는 이렇게 주어집니다.

로마 숫자 문자열 s가 주어졌을 때, 이 값을 정수로 변환해 반환합니다.

로마 숫자에서 사용하는 문자는 7개입니다.

문자	값
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

예시는 이렇습니다.

• s = "III" → 3
• s = "LVIII" → 58
• s = "MCMXCIV" → 1994

제약은 다음과 같습니다.

• 1 <= s.length <= 15
• s는 I, V, X, L, C, D, M으로만 구성
• s는 [1, 3999] 범위의 유효한 로마 숫자임이 보장됨

핵심은 로마 숫자가 보통 큰 값에서 작은 값 순서로 더해지지만, 일부 조합은 작은 값이 큰 값 앞에 오면 빼야 한다는 점입니다. 이 글에서는 감산 조합을 직접 처리하는 풀이부터, 왼쪽에서 오른쪽으로 보며 다음 문자를 비교하는 풀이, 그리고 오른쪽에서 왼쪽으로 스캔하는 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

감산 규칙부터 정리하기

로마 숫자는 대부분 값을 더하면 됩니다.

VIII = V + I + I + I = 5 + 1 + 1 + 1 = 8
LXV  = L + X + V     = 50 + 10 + 5    = 65

하지만 다음 6개 조합은 앞의 작은 값을 빼서 계산합니다.

조합	값
IV	4
IX	9
XL	40
XC	90
CD	400
CM	900

예를 들어 MCMXCIV는 이렇게 나눌 수 있습니다.

M + CM + XC + IV
= 1000 + 900 + 90 + 4
= 1994

즉 이 문제는 현재 문자를 더할지, 다음 문자와 묶어 감산 조합으로 처리할지를 판단하는 문제입니다.

Phase 1. 감산 조합을 직접 먼저 찾기

가장 직관적인 방법은 2글자 감산 조합을 테이블로 들고 있다가, 현재 위치에서 먼저 확인하는 것입니다.

fun romanToInt(s: String): Int {
    val values = mapOf(
        "I" to 1,
        "V" to 5,
        "X" to 10,
        "L" to 50,
        "C" to 100,
        "D" to 500,
        "M" to 1000,
        "IV" to 4,
        "IX" to 9,
        "XL" to 40,
        "XC" to 90,
        "CD" to 400,
        "CM" to 900,
    )

    var i = 0
    var answer = 0

    while (i < s.length) {
        if (i + 1 < s.length) {
            val two = s.substring(i, i + 2)
            val pairValue = values[two]
            if (pairValue != null) {
                answer += pairValue
                i += 2
                continue
            }
        }

        answer += values[s[i].toString()]!!
        i++
    }

    return answer
}

MCMXCIV를 따라가면:

• M은 감산 조합이 아니므로 1000 더함
• CM은 감산 조합이므로 900 더하고 두 칸 이동
• XC는 감산 조합이므로 90 더하고 두 칸 이동
• IV는 감산 조합이므로 4 더하고 두 칸 이동

최종 결과는 1994입니다.

이 방식은 문제 설명을 거의 그대로 코드로 옮긴 형태라 이해하기 쉽습니다. 다만 IV, IX, XL, XC, CD, CM을 별도로 모두 나열해야 하고, 매번 부분 문자열을 만들어 확인한다는 점이 조금 번거롭습니다.

시간 복잡도는 O(n), 공간 복잡도는 고정 크기 테이블만 쓰므로 O(1)입니다.

Phase 2. 왼쪽에서 오른쪽으로 보며 다음 값과 비교하기

감산 조합을 따로 외우지 않아도, 더 일반적인 규칙으로 처리할 수 있습니다.

현재 값이 다음 값보다 작으면 현재 값은 더하는 값이 아니라 빼는 값입니다.

IV  -> I(1) < V(5)  -> -1 + 5 = 4
IX  -> I(1) < X(10) -> -1 + 10 = 9
XC  -> X(10) < C(100) -> -10 + 100 = 90

코드는 이렇게 됩니다.

fun romanToInt(s: String): Int {
    var answer = 0

    for (i in s.indices) {
        val current = valueOf(s[i])
        val next = if (i + 1 < s.length) valueOf(s[i + 1]) else 0

        if (current < next) {
            answer -= current
        } else {
            answer += current
        }
    }

    return answer
}

private fun valueOf(ch: Char): Int {
    return when (ch) {
        'I' -> 1
        'V' -> 5
        'X' -> 10
        'L' -> 50
        'C' -> 100
        'D' -> 500
        'M' -> 1000
        else -> error("Invalid roman character: $ch")
    }
}

MCMXCIV를 이 규칙으로 계산해 봅시다.

문자	다음 문자	판단	누적
M (1000)	C (100)	1000 >= 100, 더함	1000
C (100)	M (1000)	100 < 1000, 뺌	900
M (1000)	X (10)	1000 >= 10, 더함	1900
X (10)	C (100)	10 < 100, 뺌	1890
C (100)	I (1)	100 >= 1, 더함	1990
I (1)	V (5)	1 < 5, 뺌	1989
V (5)	없음	더함	1994

이 풀이의 장점은 감산 조합을 직접 나열하지 않아도 된다는 점입니다. 유효한 로마 숫자만 들어온다는 조건이 있으므로, current < next인 경우를 감산으로 처리해도 충분합니다.

참고: 이 코드는 유효하지 않은 로마 숫자를 검증하는 코드가 아닙니다. 문제에서 입력이 유효한 로마 숫자임을 보장하기 때문에 변환에만 집중합니다.

시간 복잡도는 O(n), 추가 공간은 O(1)입니다.

Phase 3. 오른쪽에서 왼쪽으로 스캔하기

같은 규칙을 오른쪽에서 왼쪽으로 보면 더 자연스럽게 표현할 수도 있습니다.

오른쪽부터 보면서, 현재 값이 오른쪽에서 이미 본 값보다 작으면 빼고, 그렇지 않으면 더합니다.

fun romanToInt(s: String): Int {
    var answer = 0
    var maxOnRight = 0

    for (i in s.lastIndex downTo 0) {
        val current = valueOf(s[i])

        if (current < maxOnRight) {
            answer -= current
        } else {
            answer += current
            maxOnRight = current
        }
    }

    return answer
}

private fun valueOf(ch: Char): Int {
    return when (ch) {
        'I' -> 1
        'V' -> 5
        'X' -> 10
        'L' -> 50
        'C' -> 100
        'D' -> 500
        'M' -> 1000
        else -> error("Invalid roman character: $ch")
    }
}

MCMXCIV를 오른쪽에서 왼쪽으로 따라가면:

문자	현재 값	오른쪽 최대값	판단	누적
V	5	0	더함	5
I	1	5	뺌	4
C	100	5	더함	104
X	10	100	뺌	94
M	1000	100	더함	1094
C	100	1000	뺌	994
M	1000	1000	더함	1994

왼쪽에서 오른쪽으로 볼 때는 "다음 값"을 매번 확인해야 합니다. 반대로 오른쪽에서 왼쪽으로 보면, 지금 값이 오른쪽의 큰 값 앞에 놓인 작은 값인지 maxOnRight 하나로 판단할 수 있습니다.

개인적으로는 Phase 2가 가장 직관적인 구현이고, Phase 3은 감산 규칙을 불변식으로 설명하기 좋습니다. 둘 다 O(n) / O(1)입니다.

왜 current < next면 빼도 되나요?

로마 숫자는 기본적으로 큰 값에서 작은 값 순서로 작성됩니다.

LXIII = 50 + 10 + 1 + 1 + 1 = 63

그런데 작은 값이 큰 값 바로 앞에 오면, 그 작은 값은 독립적으로 더하는 값이 아니라 큰 값에서 빼는 값입니다.

IV = 5 - 1
IX = 10 - 1
XL = 50 - 10
CM = 1000 - 100

따라서 왼쪽에서 오른쪽으로 스캔할 때:

• current >= next이면 현재 값은 그대로 더함
• current < next이면 현재 값은 다음 큰 값에서 빠지는 값이므로 뺌

이 규칙으로 감산 조합을 모두 처리할 수 있습니다.

문제에서 유효한 로마 숫자만 들어온다고 보장하므로, IL 같은 잘못된 입력을 따로 검증할 필요는 없습니다. 실무용 로마 숫자 파서라면 유효성 검증을 따로 넣어야 하지만, 이 문제의 목표는 검증이 아니라 변환입니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
"I"	1	한 글자 입력
"III"	3	같은 작은 값 반복
"IV"	4	I가 V 앞에 있어 감산
"IX"	9	I가 X 앞에 있어 감산
"LVIII"	58	L + V + I + I + I
"XL"	40	X가 L 앞에 있어 감산
"MCMXCIV"	1994	M + CM + XC + IV
"MMMCMXCIX"	3999	문제 범위의 최댓값

특히 "MCMXCIV"처럼 감산 조합이 여러 번 섞인 입력을 꼭 확인해 보는 것이 좋습니다. 단순히 모든 문자를 더하기만 하면 1000 + 100 + 1000 + 10 + 100 + 1 + 5 = 2216이 되어 틀립니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
감산 조합 직접 처리	O(n)	O(1)	문제 설명을 그대로 옮긴 형태, 2글자 조합을 별도 관리
왼쪽→오른쪽 다음 값 비교	O(n)	O(1)	current < next면 빼는 가장 직관적인 풀이
오른쪽→왼쪽 최대값 비교	O(n)	O(1)	오른쪽의 큰 값 앞에 놓인 작은 값을 빼는 방식

마무리

1. 로마 숫자 변환의 핵심은 감산 규칙입니다 — 작은 값이 큰 값 앞에 오면 더하지 않고 빼야 합니다
2. 왼쪽에서 오른쪽으로 볼 때는 current < next인지 확인하면 됩니다 — 이 조건 하나로 IV, IX, XL, XC, CD, CM을 모두 처리할 수 있습니다
3. 오른쪽에서 왼쪽으로 볼 때는 오른쪽에서 본 최대값보다 현재 값이 작은지만 보면 됩니다 — maxOnRight 하나로 감산 여부를 판단합니다
4. 입력 유효성 검증은 이 문제의 범위가 아닙니다 — LeetCode가 유효한 로마 숫자만 준다고 보장하므로 변환 로직에 집중하면 됩니다
5. 최종 복잡도는 O(n) 시간, O(1) 공간입니다 — 입력 길이가 최대 15라 성능보다 규칙을 정확히 코드로 옮기는 것이 핵심입니다