로마 숫자가 주어졌을 때 이를 정수로 변환해야 하는 경우가 있습니다. 로마 숫자는 일반적으로 왼쪽에서 오른쪽으로 큰 값부터 작은 값 순서로 기호를 배치하며, 유일한 예외는 어떤 기호보다 1 작은 값을 나타낼 때입니다. 주요 로마 숫자 기호와 그 의미는 다음과 같습니다.
'M': 1000
'D': 500
'C': 100
'L': 50
'X': 10
'V': 5
'I': 1
예를 들어 입력이 "MCLXVI"라면 출력은 1166이 됩니다. M = 1000, C = 100으로 합계는 1100이 되고, 여기에 L = 50, X = 10, VI = 6을 더하면 총 1166이 됩니다.
문제 해결 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
위에 정의한 대로 기호별 값 딕셔너리를 준비합니다.
결과값 ans를 0으로 초기화하고, n에는 문자열의 길이를 저장합니다.
enumerate()로 문자열의 각 인덱스 idx와 문자 c를 순회하며 다음을 수행합니다.
idx가 n - 1보다 작고, 현재 문자의 값이 다음 문자의 값보다 작다면 ans에서 d[c]를 뺍니다.
그렇지 않으면 ans에 d[c]를 더합니다.
최종적으로 ans를 반환합니다.
작동 원리: 감산 표기법
이 알고리즘의 핵심은 감산 표기법(subtractive notation) 처리입니다. IV(4), IX(9), XL(40), CM(900)처럼 작은 값의 기호가 큰 값의 기호 앞에 오면 두 값을 빼야 합니다. 코드에서는 현재 문자의 값이 바로 뒤 문자의 값보다 작은 경우에만 값을 빼고, 그 외의 경우에는 더하는 방식으로 이 규칙을 자연스럽게 처리합니다.
파이썬 구현 예제
class Solution:
def solve(self, numeral):
d = {"M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1}
ans = 0
n = len(numeral)
for (idx, c) in enumerate(numeral):
if idx < n - 1 and d[c] < d[numeral[idx + 1]]:
ans -= d[c]
else:
ans += d[c]
return ans
ob = Solution()
numeral = "MCLXVI"
print(ob.solve(numeral))
입력
"MCLXVI"
출력
1166
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 로마 숫자를 효율적으로 정수로 변환할 수 있습니다.