개요
이 튜토리얼에서는 1부터 3999 사이의 로마 숫자를 10진수(정수)로 변환하는 C++ 프로그램을 작성하는 방법을 살펴봅니다.
임의의 로마 숫자가 입력으로 주어졌을 때, 이를 해당하는 10진수 값으로 변환하는 것이 목표입니다.
로마 숫자 변환의 기본 원리
로마 숫자는 다음 일곱 가지 기호로 구성되며, 각 기호는 고유한 값을 가집니다.
- I = 1
- V = 5
- X = 10
- L = 50
- C = 100
- D = 500
- M = 1000
일반적으로 기호의 값을 왼쪽에서 오른쪽으로 더해가지만, 작은 값이 큰 값 앞에 위치하는 경우(예: IV, IX, XL, CM)에는 단순히 더하는 대신 두 값의 차를 계산해야 합니다. 이러한 감산 규칙을 올바르게 처리하는 것이 변환 알고리즘의 핵심입니다.
알고리즘 접근 방식
- 각 로마 숫자 문자에 해당하는 정수 값을 반환하는 함수를 작성합니다.
- 문자열을 순회하면서 현재 문자와 다음 문자의 값을 비교합니다.
- 현재 값이 다음 값보다 크거나 같으면 현재 값을 결과에 더합니다.
- 현재 값이 다음 값보다 작으면 두 값의 차를 결과에 더하고, 이미 처리된 다음 문자를 건너뜁니다.
C++ 구현 예시
#include<bits/stdc++.h>
using namespace std;
// 문자의 10진수 값 계산
int value(char r){
if (r == 'I')
return 1;
if (r == 'V')
return 5;
if (r == 'X')
return 10;
if (r == 'L')
return 50;
if (r == 'C')
return 100;
if (r == 'D')
return 500;
if (r == 'M')
return 1000;
return -1;
}
// 주어진 로마 숫자의 10진수 값 계산
int convert_decimal(string &str){
int res = 0;
for (int i=0; i<str.length(); i++){
// 현재 문자의 값 가져오기
int s1 = value(str[i]);
if (i+1 < str.length()){
int s2 = value(str[i+1]);
if (s1 >= s2){
res = res + s1;
}
else{
res = res + s2 - s1;
i++;
}
}
else{
res = res + s1;
}
}
return res;
}
int main(){
string str ="MCMIV";
cout << "Integer form:"
<< convert_decimal(str) << endl;
return 0;
}
실행 결과
Integer form:1904
코드 동작 설명
예제 입력 MCMIV는 다음과 같이 해석됩니다.
- M = 1000
- CM = 1000 − 100 = 900
- IV = 5 − 1 = 4
따라서 최종 결과는 1000 + 900 + 4 = 1904가 됩니다. 이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 입력 길이에 관계없이 효율적으로 동작합니다.